% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.4 for LaTeX2e as of 16. April 2010
%
\documentclass{llncs}
\usepackage{mathtools}
\usepackage{changepage}



%
%\usepackage{makeidx}  % allows for indexgeneration
%
\begin{document}
\pagenumbering{arabic}
\pagestyle{plain}
\mainmatter              % start of the contributions
%
\title{Complexity of Dense Bicluster Editing Problems}
%
\titlerunning{Bicluster Editing}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{Jan Baumbach\inst{1}, Jiong Guo\inst{2}
\and Peng Sun \inst{3}}
%
\authorrunning{Jan Baumbach et al.} % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Jan Baumbach, Jiong Guo and Peng Sun}
%
\institute{
Institute for Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark \\
\email{jbaumbac@imada.sdu.dk}
\and
MMCI Cluster of Excellence, Campus E1 7, 66123 Saarbr{\"u}cken, Germany\\
\email{jguo@mmci-uni.saarland.de}
\and
Max Planck Institute for Informatics, Campus E1 4, 66123 Saarbr{\"u}cken, Germany\\ 
\email{psun@mpi-inf.mpg.de}
\thanks{Supported by the DFG Cluster of Excellence MMCI.}
}


\maketitle              % typeset the title of the contribution

\begin{abstract}
Given a density measure $\Pi$, an undirected graph $G$ and a nonnegative integer $k$, a $\Pi$-CLUSTER EDITING problem is to decide whether $G$ can be modified into a graph where all connected components are $\Pi$-cliques, by at most $k$ edge modifications. Previous studies have been conducted on the complexity and fixed-parameter tractability (FPT) of $\Pi$-CLUSTER EDITING based on several different density measures. However, whether these conclusions hold on bipartite graphs is yet to be examined. In this paper, we focus on three different density measures for bipartite graphs: (1) having at most $s$ missing edges for each vertex ($s$-biplex), (2) having average degree at least $|V| -s$ (average-$s$-biplex) and (3) having at most $s$ missing edges within a single disjoint component ($s$-defective biclique). First, the NP-completeness of the three problems is discussed and afterwards we show all these problems are fixed-parameter tractable with respect to the parameter $(s,k)$.
\keywords{Bicluster editing, Parameterized complexity, Data reduction, NP-hardness}
\end{abstract}
%

\section{Introduction}
Graph-based data clustering methodologies have been of great importance in the scientific analyses of the real-world data, ranging from biological to social networks. In most scenarios, data entities are modeled as vertices and a certain function is defined to quantify the ``relationship" between two vertices (e.g. similarities). Thresholds specified by systems or users are then used to model the edges of the graph. The clustering problem is usually defined mathematically as a ``partition" of the whole vertex set into different dense subsets, so-called \textit{clusters}, such that there are as few edges as possible between different clusters and as few missing edges as possible within clusters. The problem could also be viewed from the graph modification angle, i.e., to modify the graph by edge insertions and deletions into a $\Pi$-cluster graph, the so-called $\Pi$-CLUSTER EDITING. Here, a graph is a $\Pi$-cluster graph, if each of its connected components satisfies $\Pi$, where $\Pi$ is a certain density measure.

The most famous problem among the $\Pi$-CLUSTER EDITING is CLUSTER EDITING, where $\Pi$ is ``being a clique". CLUSTER EDITING has been extensively studied and proved as NP-complete among the earliest NP-complete problems \cite{shamir2004cluster,bansal2004correlation}. Successful applications of the algorithms for CLUSTER EDITING could be found in the field of computational biology \cite{wittkop2010partitioning} and machine learning \cite{bansal2004correlation}. In terms of parameterized complexity, CLUSTER EDITING is proved to be solved in $O(1.83^k+|E|)$ time \cite{bocker2009going} and several different data reduction schemes have been derived \cite{cao2010cluster,chen20122,fellows2007efficient,guo2009more}. Furthermore, the current best approximation factor for CLUSTER EDITING is 2.5 \cite{van2005deterministic}. In computational biology, a number of applicable heuristic algorithms have also been designed \cite{wittkop2007large,wittkop2011comprehensive}.

However, in some real-world applications, ``being a clique" is increasingly criticized as over-restrictive \cite{seidman1978graph}. Thus some relaxed models might be more advantageous in a variety of application scenarios. Theoretical studies have also been conducted on relaxed versions of CLUSTER EDITING. Guo \textit{et al.}\cite{guo2010more} studied the fixed-parameter tractability of $s$-PLEX EDITING. In another study, Guo \textit{et al.} extended their research further to several other relaxed models: $s$-defective cliques, average-$s$-plexes and $\mu$-cliques \cite{guo2011editing}, in which the NP-completeness and the fixed-parameter tractability are proved.

In some real-world scenarios which data contains information in more than one dimension, the standard clustering model is not so powerful. For instance, the microarray data analysis requires a simultaneous clustering on rows (genes) and columns (conditions) to find consistent behaviors for groups of genes under a certain number of conditions. The traditional clustering model, which clusters data of one dimension, is not feasible for such scenarios where data from different sources must be clustered together simultaneously. The concept of ``biclustering" was thus introduced by Cheng and Church \cite{cheng2000biclustering}. Note that biclustering problems can be easily modeled as clustering problems on bipartite graphs by forming similarities between two different sets of vertices, described as follows:

\begin{adjustwidth}{1cm}{1cm}
BICLUSTER EDITING\\
\textbf{Input:} A bipartite graph $G=(U,V,E)$ and an integer $k>0$.\\
\textbf{Question:} Can $G$ be converted into a \textit{bicluster graph} where every connected component is a biclique, by at most $k$ edge insertions and deletions?
\end{adjustwidth}

A biclique is a bipartite graph with all possible edges. Though not so extensively studied as CLUSTER EDITING, several theoretical conclusions of bicluster editing have been published regarding parameterized tractability \cite{guo2008improved} and approximation results \cite{ailon2010improved}. Applications other than microarray data analysis can be found mostly in the computational biology field, for instance, biomedical data analysis \cite{sun2012integrated}, drug adverse events prediction \cite{harpaz2010biclustering} and etc.. Similarly, by relaxing the criteria of ``biclique" in different directions, $\Pi$-BICLUSTER EDITING can be yielded:

\begin{adjustwidth}{1cm}{1cm}
%$\Pi$-BICLUSTER EDITING\\
\textbf{Input:} A bipartite graph $G=(U,V,E)$ and an integer $k>0$.\\
\textbf{Question:} Can $G$ be converted into a $\Pi$-\textit{bicluster graph}, where every connected component is a $\Pi$-biclique, by at most $k$ edge insertions and deletions?
\end{adjustwidth}

Here in our study, we focus on the three cases of $\Pi$-BICLUSTER EDITING: (1) $s$-biplex, (2) average-$s$-biplex and (3) $s$-defective biclique, and provide both NP-complete and FPT results.

\section{Problem Definitions and Results}
An undirected graph $G = (U,V,E) $, where $U$ and $V$ are two sets of vertices and $E$ is the set of edges, is a \textit{bipartite graph} if $\forall e \in E$, edge $e$ has exactly one end vertex in $U$ and the other end vertex in $V$. Let $W = U\cup V$. For an arbitrary $W' \subseteq W$, the \textit{induced subgraph} $G[W']$ is the subgraph over the vertex set $W'$ with the edge set $\{\{u,v\}\in E | u, v\in W'\}$. An induced subgraph $G[W'] = (U',V',E')$ is a biclique if $\forall u \in U'$ and $\forall v \in V'$, we have $\{u, v\} \in E$. The \textit{open neighborhood} $N(v)$ of $v \in W$ is the set of vertices that are adjacent to $v$ in $G$. The \textit{degree} of a given vertex $v$ is denoted by $d(v)$, referring to the cardinality of $N(v)$. The \textit{closed neighborhood} of $v$ is denoted by $N[v]$, i.e., $N[v]=N(v)\cup \{v\}$. The open and closed neighborhoods of a set of vertices $W'\subseteq W$ are defined as $N(W')= \bigcup_{u\in W'} N(u) \backslash W' $ and $N[W'] = N(W') \cup W'$, respectively.  Let $W' \subseteq W$, we use $G - W'$ as the abbreviation for $G[W\backslash W']$ and for a vertex $v \in W$, let $G-v$ denote $G-\{v\}$. If $G-v$ has more connected components than $G$, then we call $v$ as a \textit{cut vertex}. Similarly, let $E'$ be a set of edges, then $G-E'$ denotes the graph $G' = (U,V, E\backslash E')$. For a graph $G = (U,V,E)$, denote $\overline{E} = \{\{u,v\}| u\in U \wedge v\in V \wedge \{u,v\} \notin E\}$ as the set of \textit{missing edges}. A pair of vertices $\{u,v\}$ is called a \textit{missing edge} if $\{u,v\}\in \overline{E}$. For two sets of vertices $X$ and $Y$, let $E(X,Y) $ be the set of edges between $X$ and $Y$, i.e., $E(X,Y)= \{\{u,v\}\ |\ u\in X \ \wedge\ v\in Y \ \wedge \ \{u,v\} \in E\}$. For a vertex set $X$, denote $E(X)$ as the abbreviation for $E(X,X)$. For a set of vertex $X'$ and a bipartite graph $H = (X,Y,E)$, denote the intersection between $X'$ and $H$ as the set of common vertices, i.e., $X' \cap H = (X'\cap X)\cup (X'\cap Y)$.

%A problem is \textit{fixed-parameter tractable} (FPT) with respect to a certain parameter $k$, if there is an algorithm that decides the problem in $f(k)\cdot n^{O(1)}$ time. Here, $n$ denotes the size of the input and $f$ is a computable function. The framework of \textit{fixed-parameter tractability} was developed by Downey and Fellows \cite{fellows1999parameterized}. A crucial tool in the development of fixed-parameter algorithms is polynomial-time preprocessing data reduction. Its goal is for a given instance $x$ with parameter $k$, to transform the problem into a new instance $x'$ with parameter $k'$, such that the size of the new instance $x'$ is upper-bounded by some function only depending on $k$. The instance $(x,k)$ is a yes-instance if and only if $(x',k')$ is a yes-instance and $k'\leq k$. The reduced instance must be computable in polynomial time. The whole data reduction process is called \textit{reduction to a problem kernel} or \textit{kernelization} and the reduced instance is called \textit{problem kernel}.

An $s$-biplex is a connected bipartite graph $G =(U,V, E)$ with $d(u) \geq |V| - s$ for all $u\in U$ and $d(v) \geq |U| - s$ for all $v\in V$. Note that a normal biclique is thus a $0$-biplex. A bipartite graph $G$ is called an \textit{$s$-biplex cluster graph} if all its connected components are $s$-biplexes. Therefore, $s$-BIPLEX EDITING is the special case of bicluster editing with $\Pi$ equal to ``$s$-biplex". In this paper, the NP-completeness of s-BIPLEX EDITING is shown. Then the sizes of \textit{minimal forbidden induced subgraphs} are upper-bounded by $O(s)$ and a branching strategy can be derived which indicates the FPT of $s$-BIPLEX EDITING.

In general graphs, average-$s$-plex is proposed as a ``density measure" defined as the mean of the degrees of all vertices in a given graph \cite{guo2010more}. In a bipartite graph, we define the \textit{average degree} for two vertex sets separately: $\overline{d}_U=|E|/|U|$ and $\overline{d}_V=|E|/|V|$. A connected graph $G = (U,V,E)$ is thus an \textit{average-s-biplex} if $\overline{d}_U\geq |V|-s$ and $\overline{d}_V\geq |U|-s$, with $1\leq s\leq \min\{|U|,|V|\}$. This density measure can be considered as a further relaxation of $s$-biplex, with no requirement on the \textit{minimum} degree. In this work, we show the NP-completeness of AVERAGE-$s$-BIPLEX EDITING. Afterwards, a reduction to a more general problem is conducted, followed by a polynomial-time kernelization procedure which produces a graph with at most $2k((s+1)(4k+6s)+1)$ vertices. This implies FPT for AVERAGE-$s$-BIPLEX EDITING.

The concept of \textit{defective clique} has been reported previously to be useful in biological network analysis \cite{yu2006predicting}. NP-completeness and FPT of $s$-DEFECTIVE CLIQUE EDITING and DELETION are already known \cite{guo2011editing}. A connected bipartite graph $G = (U,V,E)$ is an $s$-defective biclique if $|E| \geq |U|\cdot |V| -s$. We prove that $s$-DEFECTIVE BICLUSTER EDITING is NP-complete. Then, the sizes of minimal forbidden induced subgraphs of $s$-defective bicluster graphs are shown to be bounded by $2s+3$, which leads directly to the FPT of $s$-DEFECTIVE BICLUSTER EDITING with respect to the parameter $(s,k)$. For more information on parameterized complexity, we refer to \cite{fellows1999parameterized} and \cite{niedermeier2006invitation}. Due to limited space, some proofs are deferred to Appendix.

\section{s-Biplexes}

\subsection{NP-Completeness}
In this section, we show the NP-completeness of $s$-BIPLEX EDITING by a reduction from 3-EXACT-3-COVER.

\begin{theorem}
For every constant $s\geq 0$, $s$-BIPLEX EDITING is NP-complete.
\label{theorem:01}
\end{theorem}
\begin{proof}
If $s$=0, then the problem is equivalent to BICLUSTER EDITING and thus is NP-complete. For every $s\geq 1$, we reduce the NP-complete 3-EXACT-3-COVER (3X3C), where given a collection $\mathcal{C}$ of triplets (a set of 3 elements is called a triplet) from an element set $A=\{a_1,a_2,a_3,...,a_{3n}\}$ such that each element of $A$ is a member of at most three triplets, one asks to find out a sub-collection $\mathcal{I}\subseteq \mathcal{C}$ of size $n$ that covers $A$, i.e., every element of $A$ appears in some triplet in $\mathcal{I}$. The set $\mathcal{I}$ is called an ``exact cover".

We construct an $s$-BIPLEX EDITING instance as follows: Let $m = (72+s)n $. A bipartite graph $G = (U,V,E)$ is then constructed, based on the following procedure: For each element in $A$, one corresponding vertex is created in $U$, and for each triplet $S\in \mathcal{C}$, a set of $m$ vertices is added to $U$. The same construction is performed to create vertices in $V$, that is: $U=U_1 \cup U_2$, $V=V_1 \cup V_2$, $U_1=\{u_1,u_2,...,u_{3n}\}$, $V_1=\{v_1,v_2,...,v_{3n}\}$, $U_2=\bigcup_{S\in \mathcal{C}} \{u_{S_1},u_{S_2},...,u_{S_m}\}$, $V_2=\bigcup_{S\in \mathcal{C}} \{v_{S_1},v_{S_2},...,v_{S_m}\}$.

The edge set $E$ in $G$ consists of five subsets: First, we connect every $u_i\in U_1$ to its corresponding $v_i\in V_1$, $1\leq i\leq 3n$. Second, for each triplet $S\in \mathcal{C}$, let $S = \{a_x,a_y,a_z\}$, $(1\leq x,y,z \leq 3n)$. We connect $u_i \in U_1$ and $v_j\in V_1$ for all $i,j \in \{x,y,z\}$ with $i\neq j$.  Third, between $U_2$ and $V_2$, for each $S\in \mathcal{C}$, denote $U_S^m = \{u_{S_1}, u_{S_2},,...,u_{S_m} \}$ and $V_S^m = \{v_{S_1},v_{S_2},...,v_{S_m}\}$. We connect $u_{S_i} \in U_S^m $ to $v_{S_j} \in V_S^m$ for all $1\leq i,j\leq m$. Finally, for each $S = \{a_x,a_y,a_z\} \in \mathcal{C}$, $(1\leq x,y,z \leq 3n)$, every $u_i \in U_1 (i \in \{x,y,z\})$ is connected to all vertices in $V_S^m \subseteq V_2$, and every $v_i \in V_1$ $(i \in \{x,y,z\})$ is connected to all vertices in $U_S^m \subseteq U_2$. More precisely: $ E=\bigcup_{i=1}^5 E_i$, $E_1=\{\{u_i,v_i\}| \ i=1,...,3n\}$, $E_2=\{\{u_i,v_j\}| \ \exists S = \{a_x,a_y,a_z\} \in \mathcal{C} \ \wedge \  i,j \in \{x,y,z\} \ \wedge \  i\neq j\}$, $E_3=\{\{u_{S_i},v_{S_j} \} |\ \exists S \in \mathcal{C} \ \wedge \  u_{S_i} \in U_S^m \ \wedge \ v_{S_j} \in V_S^m \}$, $E_4=\{\{u_i,v_{S_j} \} | \ \exists S= \{a_x,a_y,a_z\} \in \mathcal{C} \ \wedge \  i\in\{x,y,z\} \ \wedge \  v_{S_j} \in V_S^m \}$, $E_5=\{\{v_i,u_{S_j} \} | \ \exists S= \{a_x,a_y,a_z\} \in \mathcal{C} \ \wedge \  i\in\{x,y,z\} \ \wedge \ u_{S_j} \in U_S^m  \} $.


For each triplet set $S\in \mathcal{C}$, we denote: $U_S=\{u_x, u_y, u_z| \{a_x,a_y,a_z\} \in S \}$, $V_S=\{v_x, v_y, v_z| \{a_x,a_y,a_z\} \in S \}$, $W_S=U_S \cup V_S$, $U_S^m = \{u_{S_1}, ..., u_{S_m}\}$, $V_S^m = \{v_{S_1}, ..., v_{S_m}\}$, $W_S^m = U_S^m \cup V_S^m $.

Obviously, the construction can be carried out in polynomial time. Let $M=2m(3|\mathcal{C}|-3n)$ and $N=|E_2|-6n$. The parameter $k$ is equal to $M+N$. For the rest of the proof, refer to Appendix.
\qed
\end{proof}

\subsection{Forbidden Induced Subgraphs}

In this section, we describe a set of \textit{forbidden induced subgraphs} $\mathcal{G}_F$, that a graph $G$ is an $s$-biplex cluster graph if and only if $G$ does not contain any induced subgraphs in $\mathcal{G}_F$. If $s=0$, then we have BICLUSTER EDITING problem and the forbidden subgrah is a path of four vertices. If $s\geq1$, the structures of forbidden induced subgraphs are much more complex and we are facing with an exponentially increasing number of different possibilities. To solve the problem, we show in the following that the sizes of forbidden induced graphs are bounded by $O(s)$ vertices. Based on this characterization, a branching strategy solving $s$-BIPLEX EDITING can be established.

We start with some preliminaries. A connected induced subgraph $H=(R,T,E')$ is \textit{minimal forbidden induced subgraph} if $H$ is not an $s$-biplex but every induced proper subgraph of $H$ is an $s$-biplex cluster graph. We call a vertex $v$ in $H$ ``$forbidden$" if $v$ is incident to more than $s$ missing edges. A subset of vertices $R'$ is called ``\textit{forbidden subset}" if $R'$ contains at least one forbidden vertex. To show the upper-bound for minimal forbidden induced subgraphs, two distinct cases are studied separately: (1) subgraph $H$ contains forbidden vertex (vertices) only in $R$ (or $T$), and (2) $H$ contains forbidden vertices in both $R$ and $T$. We first prove four claims regarding the properties of a minimal forbidden induced subgraph. Next, as a summary, we show that every minimal forbidden induced subgraph of biplexes contains at most $3s+3$ vertices in both the two cases mentioned above, for all $s\geq 1$. 

\begin{lemma}

Let $H = (R,T,E')$ be a minimal forbidden induced subgraph. If $R$ is a forbidden subset, then $\min\limits_{u\in R}\{d(u)\} = |T| - s -1.$
\label{lemma:01}
\end{lemma}



\begin{lemma}
Let $H = (R,T,E')$ be a minimal forbidden induced subgraph. If $H$ has forbidden vertices both in $R$ and $T$, then $H$ can only be a path of length $2s+4$, and only the two endpoints of the path are forbidden vertices.
\end{lemma}

\begin{proof}
First we prove the claim that $H$ contains no more than two forbidden vertices if $H$ has forbidden vertices both in $R$ and $T$. By contradiction, assume there are $>2$ forbidden vertices in $H$. Since we know that in every graph, there are at least 2 non-cut vertices. Let $u,v$ be the 2 non-cut vertices. We have 6 cases with respect to $u$ and $v$:

Case i: $u,v$ are both forbidden vertices, and $u,v \in R$. Then we can remove $u$ without separating $H$. In the subgraph $H-u$, we have $d_{H-u}(v) = |T| -s-1$ and $H-u$ is also forbidden, contradicting with minimal forbidden induced subgraph. If $u,v\in T$, same proof applies.

Case ii: $u,v$ are both non-forbidden vertices, and $u,v\in R$. Since $R$, $T$ are both forbidden subsets, there exists a forbidden vertex $w \in R$, such that $d(w) = |T|-s-1$. The subgraph $H-u$ is also forbidden since $d_{H-u}(w) = |T|-s-1$. If $u,v\in T$, the same proof applies.

Case iii: $u$ is a forbidden vertex, $v$ is a non-forbidden vertex and $u,v \in R$. Then just remove $v$ and $H-v$ is still forbidden.

Case iv: $u$ is a forbidden vertex in $R$, $v$ is a non-forbidden vertex in $T$. Since $R$, $T$ are both forbidden subsets, there exists a vertex $w\in T$, such that $d(w) = |R|-s-1$. We remove $v$ from $T$. Then $d_{H-v}(w) = |R|-s-1$ and thus $H-v$ is still forbidden.

Case v: $u$ is a non-forbidden vertex in $U$ and $v$ is a non-forbidden vertex in $V$. A proof similar to Case iv applies.

Case vi: $u$ is a forbidden vertex in $R$, $v$ is a forbidden vertex in $T$. Let $w$ be a forbidden vertex in $H$ and $w \neq u$, $w\neq v$. Without loss of generality, we assume $w\in R$. Then we can remove $u$ from $H$. Then $d_{H-u}(w) = |T|-s-1$ and thus $H-u$ is still forbidden.

To summarize the six cases, since we have two non-cut vertices and at least three forbidden vertices with at least one forbidden vertex in $R$ and at least one in $T$, we can always find a forbidden vertex $x$ and a non-cut vertex $y$ in the same vertex set (in $R$ or in $T$). Clearly, removing $y$ does not affect the property of the forbidden vertex $x$ and thus the subgraph $H-y$ is still forbidden. This contradicts with the assumption. Hence, if $H$ is a minimal forbidden induced subgraph with forbidden vertices in both $R$ and $T$, then $H$ cannot contain more than two forbidden vertices.

Next, we prove that $H$ can only be a path of $2s+4$ vertices. Let $u^*$ and $v^*$ be the two forbidden vertices in $H$. Suppose $u^* \in R$ and $v^* \in T$. Consider a third vertex $w^*$, $w^* \neq u^*$ and $w^* \neq v^*$. Clearly, such vertex $w^*$ exists. If $w^*$ is a non-cut vertex, then consider the subgraph $H-w^*$. If $w^*\in R$, in $H-w^*$, $u^*$ is still a forbidden vertex; if $w^* \in T$, then in $H-w^*$, $v^*$ is still a forbidden vertex. In either case, $H$ is not minimal. Therefore, we know that in $H$, all vertices other than $u^*$ and $v^*$ must be cut vertices. Thus in $H$, we have $|R|+|T|-2$ cut vertices. Obviously, $H$ can only be a path and $u^*$, $v^*$ can only be the two endpoints of the path in $R$ and $T$.\qed \end{proof}

\begin{lemma}
Let $H = (R,T,E')$ be a minimal forbidden induced subgraph with forbidden vertices only in $R$. Let $R_0\subseteq R$ be the subset of all forbidden vertices and $R_1= R \backslash R_0$. Let $T_0  = N(R_0)$ and $T_1 = T \backslash T_0$. Then we have:

\begin{enumerate}
\item $\forall u \in R_1$, $u$ is a cut vertex.
\item $\forall v \in T_0$, $v$ is a cut vertex.
\item If $|R_0| >1$, then $\forall u \in R_0$, $u$ is a cut vertex.
\item If $|T_0|>1$, then for an arbitrary vertex $v^* \in T_0$ , let $\mathcal{H} = \{ H_1, H_2, ... ,H_l\}$ be the set of disjoint components after removing $v^*$. Then for each $H_i =(X_i, Y_i, E_i)$, $1\leq i\leq l$, we have $X_i\cap R_1 \neq \emptyset$. 
\item There exists at least one vertex $v\in T_1$ with $d(v) = 1$. 
\end{enumerate}

\label{lemma:03}
\end{lemma}



\begin{lemma}
Let $H = (R,T,E')$ be a minimal forbidden induced subgraph with forbidden vertices only in $R$. Let $R_0\subseteq R$ be the subset of all forbidden vertices, $R_1= R \backslash R_0$. Let $T_0  = N(R_0)$ and $T_1 = T \backslash T_0$. Then we have $|R|+|T| \leq 3s+3$.
\end{lemma}
\begin{proof}
Consider an arbitrary vertex $v^*\in T_0$. By Lemma 3, $v^*$ is a cut vertex. Let $\mathcal{H} = \{H_1, H_2, ..., H_r\}$, $r>1$, $H_i = (X_i, Y_i, E_i)$ be the set of disjoint connected components after removing $v^*$. Without loss of generality, let $\{H_1, H_2, ..., H_l\}$ be the subset of $\mathcal{H}$, $l \leq r$, such that $X_i \cap R_0 \neq \emptyset$, for all $1\leq i\leq l$. We have the following two cases:

Case i. If $l\geq 2$, we know there is at least two disjoint components that intersect with $R_0$. Hence consider $\forall u \in X_1$ and $\forall v\in Y_j$ $(1< j \leq l)$, we have $\{u, v\}\notin E'$. Similarly, we have $\{u', v'\}\notin E'$, for all $u'\in X_j$ $(1<j\leq l)$ and all $v'\in Y_1$. Thus, we have $|Y_1| \leq s+1$ and $\sum\limits_{j=2}^{l} |Y_j| \leq s+1$, since otherwise we would have a $u\in R$ incident to more than $s+1$ missing edges, contradicting with Lemma 1. Because the number of missing edges incident to every vertex in $R$ cannot be larger than $s+1$, we have $|Y_1|+|T_1| \leq s+1$ and $\sum\limits_{j=2}^{l}|Y_j|+|T_1| \leq s+1$. Thus we have $|T| = |Y_1|+\sum\limits_{j=2}^{l}|Y_j|+|T_1| \leq s+1+s+1= 2s+2$. Moreover, since we know $\min\limits_{w\in T} d(w) = 1$ and $T$ does not contain forbidden vertex, we have $|R| \leq s+1$. Thus the total size of the forbidden induced subgraph $H$ is $|R| +|T| \leq 2s+2+s+1= 3s+3$.

Case ii. if $\forall v\in T_0$, we have $l=1$, then for all $v\in T_0$, the removal of $v$ will not separate $R_0$. For an arbitrary vertex $v^*$ in $T_0$, let $\mathcal{H} = \{H_1, H_2, ... H_r\}$, $H_i = (X_i, Y_i, E_i)$ be the disjoint connected components after removing $v^*$. Without loss of generality, let $R_0 \subseteq X_1$. Then $T_0\subseteq Y_1$ and we can find at least one $u^*$ with $u^*\in (N(v^*)\cap R_1)$, such that $u^*\notin N(v')$ for all $v'\in T_0$, $v'\neq v^*$. Therefore, each vertex $v^*$ in $T_0$ has at least one ``unique" neighbor in $R_1$. Thus $|T_0| \leq |R_1| \leq s+1 - |R_0| \leq s$. Moreover, we have $|T_1| \leq s+1$, since otherwise the vertices in $R_0$ would be incident to more than $s+1$ missing edges. Then the total size of the forbidden induced subgraph $H$ is $|R|+|T| \leq s+1 +s +s+1 \leq 3s+2$. In summary, the claim is proved. \qed \end{proof}


Combining Lemma 2 and Lemma 4, we have the following theorem:

\begin{theorem}
If a graph $G$ is not an s-biplex cluster graph, then we can find a forbidden subgraph in $G$ in polynomial time with the size bounded by 3s+3.
\end{theorem}

\begin{corollary}
S-BIPLEX CLUSTER EDITING is fixed-parameter tractable with respect to (s,k).
\end{corollary}

\section{Average-\textit{s}-Biplexes}
In this section, we consider the AVERAGE-\textit{s}-BIPLEX EDITING, proving its NP-completeness and its FPT with respect to parameters $(s,k)$. To show its NP-hardness, a two-step reduction is demonstrated: First, we reduce a well-known NP-complete MAXIMUM BALANCED BICLIQUE (MBB) to EQUAL-SIZE BICLUSTER EDITING, afterwards, a reduction from EQUAL-SIZE BICLUSTER EDITING to AVERAGE-\textit{s}-BIPLEX EDITING is conducted. The EQUAL-SIZE BICLUSTER EDITING (ESBE) is defined as follows:

\begin{adjustwidth}{1cm}{1cm}
\textbf{Input}: An undirected bipartite graph $G=(U,V,E)$ and two integers $k,d \geq 0$.\\
\textbf{Question}: Can $G$ be transformed by editing at most $k$ edges into $d$ disjoint bicliques $\{C_1, C_2, C_3, ..., C_d\}$, $C_i = (U_i,V_i,E_i)$, $1\leq i\leq d$, such that $|U_i| =|U_j|$ and $|V_i| = |V_j|$ for all $1\leq i,j\leq d$? 
\end{adjustwidth}
The edge deletion version of this problem requires only edge deletions.

\begin{theorem}
EQUAL-SIZE BICLUSTER EDITING is NP-complete.
\label{theorem:03}
\end{theorem}


\begin{theorem}
For every constant $s\geq 1$, AVERAGE-$s$-BIPLEX EDITING is NP-complete.
\label{theorem:04}
\end{theorem}

We present a kernalization procedure for AVERAGE-$s$-BIPLEX EDITING with respect to the parameter $(s,k)$. In order to show this, first we reduce the problem into an integer-weighted version and afterwards we describe three reduction rules that can be carried out within polynomial time.

We introduce two types of weights to describe the weighted version of AVERAGE-$s$-BIPLEX EDITING: Vertex weights and edge weights, inspired by the idea of the reduction of the weighted version of CLUSTER EDITING, i.e., for any pair of vertices that cannot be separated by $k$ edge modifications, we merge them into one ``multi-vertex". Obviously, for all vertices merged, they end up in the same average-$s$-biplex in all optimal solutions.

We denote the vertex weight as $\sigma(u)$ which keeps track of the number of vertices merged into $u$. The vertex weight of a set of vertices $S$ is defined as: $\sigma(S) = \sum\limits_{v\in S} \sigma(v)$. Moreover, let $\delta(u)$ be the subset of vertices $\{u_1, u_2, ..., u_r\}$, $r\geq 1$ that merged into $u$, i.e., $\sigma(u) = |\delta(u)|$. The edge weight, $\omega(u,v)$, is defined between two arbitrary entities (The concept ``entity" represents vertices, multi-vertices and sets of vertices), storing the number of edges between them. The degree of a vertex $u$ is defined as: $d'(u) = \omega(u,N(u))$. Thus, for a weighted bipartite graph $G= (U,V,E)$, the average degree of the vertices in $U$ is defined as: $\overline{d_{U}} = \frac{\omega(U,V)}{\sigma(U)}$.

Hence a bipartite graph $G=(U,V,E)$ is a weighted average-$s$-biplex, if $\overline{d_U} \geq \sigma(V) - s$ and $\overline{d_V}\geq \sigma(U) - s$. The weighted version of the problem can be defined as:

\begin{adjustwidth}{1cm}{1cm}
\textbf{Input:} A graph $G=(U,V,E)$, with vertex weight $\sigma(u)$ as a function: 
\begin{equation*}
\sigma (u):
\left \{ 
\begin{array}{lll}
U&\rightarrow &[\ 1,|U|\ ]\\
V&\rightarrow &[\ 1,|V|\ ]
\end{array}
\right.
\end{equation*}
and edge weight $\omega(u,v)$ as a function:
\begin{align*}
\omega(u,v): E \ \ \rightarrow \ \ [\ 1,|U||V|\ ]
\end{align*}
and a nonnegative integer $k$.\\
\textbf{Question:} With edge modifications whose total weight is at most $k$, can $G$ be edited into a weighted average-$s$-biplex cluster graph?
\end{adjustwidth}

Note that if we set $\sigma(u)\coloneqq 1$, $\delta(u) \coloneqq \{u\}$ and for each $\{u,v\}\in E$, $\omega(u,v) \coloneqq 1$, an instance of AVERAGE-$s$-BIPLEX EDITING can be easily reduced to an instance of WEIGHTED AVERAGE-$s$-BIPLEX EDITING. In this reduction, parameters $k$ and $s$ are not changed. 

The following three reduction rules are designed for WEIGHTED AVERAGE-$s$-BIPLEX EDITING, which lead to a problem kernel with no more than $2k((s+1)(4k+6s)+1)$ vertices.

\textbf{Rule 1.} Remove all connected components in $G$ that are already weighted average-$s$-biplexes.

\textbf{Rule 2.} For two vertex $u,v \in U$ or $u,v \in V$, let $S(u,v) \coloneqq N(u)\cap N(v)$. If \\$\min\{\omega(u, S(u,v)), \omega(v,S(u,v))\}>k$, then we merge $u$ and $v$, by replacing $u$ and $v$ with a new vertex $v'$, such that $v'$ satisfies: (1) $\sigma(v') = \sigma(u) + \sigma(v)$ and (2) $\omega(v',x) = \omega(u,x) + \omega(v,x)$ for every $x$ with $\{u,x\}\in E$ or $\{v,x\}\in E.$

\begin{lemma}
\textbf{Rule 2} is correct.
\label{lemma:05}
\end{lemma}



The function of Rule 2 is to merge (or replace) the vertices that we cannot afford separating. Based on the same idea, we consider another scenario: If a vertex $u$ has a large set of neighbors that only connects to $u$ but no other vertex, then we cannot possibly delete the edges between $u$ and all its ``unique" neighbors. Let $N^*(u) \subseteq N(u)$ be a set of vertices such that $\forall v\in N^*(u)$, $v$ satisfies: (1) $N(v) = \{u\}$ and (2) $\sigma(v) = 1$. Rule 3 is then presented to reduce the size of $N^*(u)$:

\textbf{Rule 3.} For each $u\in G$, if $|N^*(u)| >k$, then we replace $N^*(u)$ with a subset of vertices containing $k+1$ vertices: $\{v_0,v_1, v_2, ..., v_k\}$, such that $\omega(u,v_0) = \omega(u,N^*(u))-k$ and $\omega(u,v_i) = 1$ for all $1\leq i \leq k$.

\begin{lemma}
Rule 3 is correct.
\label{lemma:06}
\end{lemma}



\begin{theorem}
(WEIGHTED) AVERAGE-$s$-BIPLEX EDITING is fixed-parameter tractable with respect to parameter $(s,k)$ and admits a kernel of at most $2k((s+1)(4k+6s)+1)$ vertices.
\label{theorem:05}
\end{theorem}



\section{Defective Bicliques}
We prove now the NP-completeness of $s$-DEFECTIVE BICLUSTER EDITING

\begin{theorem}
For every $s\geq0$, $s$-DEFECTIVE BICLUSTER EDITING is NP-complete.
\label{theorem:06}
\end{theorem}

Next, we show the FPT of $s$-DEFECTIVE BICLUSTER EDITING by proving that for every $s\geq1$, all minimal forbidden induced subgraphs contain at most $2s+3$ vertices and hence we are able to find a minimal forbidden subgraph in polynomial time.

\begin{lemma}
For every $s\geq 1$, every minimal forbidden induced subgraph of $s$-defective bicluster graphs contains at most $2s+3$ vertices. Given a graph that is not an $s$-defective bicluster graph, a minimal forbidden induced subgraph can be found in $O((|U|+|V|)\cdot |E|)$ time.
\end{lemma}

\begin{proof}
Denote $H = (R,T,E')$ as a minimal forbidden induced subgraph of $s$-defective bicluster graph. Clearly, $H$ is connected. Towards contradiction we assume $H$ contains more than $2s+3$ vertices. We distinguish 2 cases:

Case i. There exists a cut vertex in $H$. Let $u^*\in R$ be a cut vertex. Obviously, by $s+4\leq 2s+3$ for $s\geq 1$, we can always find in $H$ a connected subgraph $H'$ such that $H'$ contains $u^*$ and other $s+3$ vertices and $u^*$ is a cut vertex in $H'$. Let $H' =(R',T',E'')$. We prove that $H'$ is forbidden. By removing $u^*$, we obtain a set of disjoint connected components $\mathcal{H} = \{H_1,H_2,...,H_l\}$, $H_i =(R_i,T_i,E_i) $. Thus, we have the number of missing edges $e_m$ in $H'$ is at least:
\begin{align*}
e_m &\geq \frac{1}{2}\sum\limits _{i=1}^{l}(|R_i|(|T'|-|T_i|)+|T_i|(|R'|-1-|R_i|))\\
    & = \frac{1}{2}\sum\limits _{i=1}^{l} |R_i||T'| + \frac{1}{2}\sum\limits _{i=1}^{l} |T_i|(|R'|-1) -
        \sum\limits _{i=1}^{l} |R_i||T_i|\\
    & =(|R'| - 1)|T'| - (|R_1||T_1| +\sum\limits _{i=2}^{l}|R_i||T_i|)\\
    & \geq (|R'|-1)|T'| - (|R_1||T_1| + (\sum\limits _{i=2}^{l}|R_i|)(\sum\limits _{i=2}^{l}|T_i|))\ \  (*)\\
    &  = (|R'|-1)|T'| - (|R_1||T_1| + (|R'|-1-|R_1|)(|T'|-|T_1|)) \\
    &  = |T_1|(|R'| -1 - |R_1|)+|R_1|(|T'| - |T_1|) \\
    & \geq |R'|+|T'| -3 \ \ \ (**)
\end{align*}

Inequality (*) holds because for any integer $a_1,b_1,a_2,b_2 >0$, we have $a_1\cdot b_1 + a_2\cdot b_2 \leq (a_1+b_1)(a_2+b_2)$. Inequality (**) is the minimum value of the function $f(|T_1|,|R_1|) = |T_1|(|R'| -1 - |R_1|)+|R_1|(|T'| - |T_1|)$, with $1\leq |R_1| \leq |R'|-1$ and $1\leq |T_1| \leq |T'|$. Thus, we have $e_m\geq s+1$. Since $|R'|+|T'| = s+4$, we have $H'$ being a forbidden subgraph, thus contradicts the assumption.

Case ii. If there is no cut vertex in $H$, then we know that $\forall v \in H$, $v$ must be incident to missing edge(s), otherwise we can just remove $v$ from $H$ without changing the forbidden subgraph property.  Let $n = |U|+|V|$, $m_0$ be the minimum ``anti-degree" (``anti-degree" is the number of missing edges incident to a given vertex) in $H$ and $m_t$ be the total number of missing edges in $H$. Hence we have the inequalities: (1) $\frac{1}{2}\cdot n \cdot m_0 \leq m_t$ and (2) $m_t-m_0\leq s$.

Inequality (1) holds because each vertex is incident to at least $m_0$ missing edges and altogether we have no more than $m_t$ missing edges. Inequality (2) holds because $H$ is a minimal forbidden subgraph and the removal of vertex $v$ will decrease the total number of missing edges by at least $m_0$. Since $H$ is minimal, $\forall u \in H$, $H-u$ is not forbidden and thus has no more than $s$ missing edges. Solving the inequalities, we have: $ n\leq \frac{2s+2m_0}{m_0} =\frac{2}{m_0}s+2 \leq 2s+2$.

Thus if $n>2s+3$, then at least one inequality above is not satisfied and hence $H$ is not a minimal forbidden induced subgraph. To locate a minimal forbidden induced subgraph, we first check if the given connected graph $G$ is an $s$-defective bicluster graph. If not, we check for each $v\in G$, the subgraph $G- v$. If $G-v$ is still not an $s$-defective bicluster graph, then we remove $v$ from $G$. Thus to find a minimal forbidden induced subgraph takes at most $O((|U|+|V|)|E|)$ time. \qed \end{proof}

\begin{theorem}
$s$-DEFECTIVE BICLUSTER EDITING is fixed-parameter tractable with respect to (s,k).
\end{theorem}



\section{Outlook}
We point out some further directions of this research topic. For all the three problems, further algorithmic improvements are necessary: For $s$-BIPLEX and $s$-DEFECTIVE BICLUSTER EDITING, a more elegant and efficient problem kernel is needed, and for average-$s$-BIPLEX EDITING, an efficient branching strategy other than brute-force is beneficial to be applied on the reduced problem kernel. Moreover, in many practical applications, for example in computational biology, high-quality heuristic algorithms should always be taken into account. Finally, it is also interesting to consider other meaningful density measures and study their classical and parameterized complexity.

%
% ---- Bibliography ----
%

\bibliographystyle{plain}
\bibliography{s-plex_PengSun}


% ---------- Appendix
\newpage
\section{Appendix}
\textit{Proof of Theorem \ref{theorem:01}}:

\begin{proof}

``$\Rightarrow$" Let $\mathcal{I} \subseteq \mathcal{C}$ be an exact cover of $A$, define: $F_1 = \{\{u_i,v_{S_j}\}|\  u_i \in U_1 \ \wedge \  v_{S_j} \in V_S^m \ \wedge\  \{u_i, v_{S_j} \} \in E \  \wedge \  S\notin \mathcal{I}  \}$, $F_2 = \{\{v_i,u_{S_j}\}|\  v_i \in V_1 \ \wedge \ u_{S_j} \in U_S^m \ \wedge \ \{u_i, v_{S_j} \} \in E  \ \wedge \  S\notin \mathcal{I}  \}$, $F_3 = E_2 \backslash \{\{u_i,v_j\}|\ \ S = \{a_x,a_y,a_z\}\in \mathcal{I} \ \wedge \ i,j \in \{x,y,z\} \ \wedge \  i\neq j\}.$

Let $F$ be the union of $F_1$, $F_2$ and $F_3$. Since in $\mathcal{I}$, each element must be contained in exactly one triplet, then in the graph $G-F$, for all vertices $u \in U_1\cup V_1$, $u$ is connected with exactly one $W_S^m$. Hence $G-F$ is a bicluster graph containing $2|\mathcal{C}|$ bicliques and clearly gives a solution to the $s$-BIPLEX EDITING instance.

Since $|\mathcal{I}| = n$, then $|\mathcal{C}|-n$ is equal to the number of ``surplus triplets", i.e., the triplets that are not in $\mathcal{I}$. Thus, we have $|F_1| = |F_2| = 3(|\mathcal{C}|-n)\cdot m = M/2$. Moreover, in $G-F$, we have $3n+6|\mathcal{I}| = 9n$ edges between $U_1$ and $V_1$, thus we can easily compute that $|F_3| = |E_1|+|E_2| - 9n = |E_2|-6n$. Denote $F$ as the set of edited edges, i.e., the set of deleted edges and inserted missing edges. We have $|F| = |F_1|+|F_2|+|F_3| = M+N$. 

``$\Leftarrow$" In the reverse direction, if there exists an optimal solution for the $s$-BIPLEX EDITING instance, let $F$ be the set of edited edges. We prove that $|F|\geq M+N$.

Let $F' = F_1\cup F_2 \cup F_3$ where $F_1$, $F_2$ and $F_3$ are defined in the ``$\Rightarrow$" direction, and thus $|F'| = M+N$. Clearly $F'$ gives a solution to the $s$-BIPLEX EDITING instance. Before proving the lower-bound on $|F|$, we first show $|F'| < m(\frac{m+1}{6})$. 

In 3X3C, each element can be covered by at most 3 triplets, thus $|\mathcal{C}|\leq 3n$. Hence $M = 2m(3|\mathcal{C}| - 3n)\leq 2m(9n - 3n) \leq 12mn$. Consider $|E_2|$, $|E_2| = 9|\mathcal{C}| - 3|\mathcal{C}| = 6|\mathcal{C}| \leq 18n$. Thus $|F'| = |F_1|+|F_2|+|F_3| = M+N = 2m(3|\mathcal{C}|-3n)+|E_2|-6n \leq 12mn +18n - 6n  = 12mn +12n = 12m \cdot \frac{m}{72+s}+ 12 \cdot \frac{m}{72+s} \leq \frac{m^2}{6} +\frac{m}{6}= m(\frac{m+1}{6})$

Let $G'$ be the resulting graph of $G$ after all edge insertions and edge deletions in $F$ are performed. We next prove the claim: For every $W_S$ and $W^m_S$, there is $s$-biplex $B$ in $G'$, such that $W^m_S \subseteq B \subseteq (W^m_S \cup W_S)$.

We proceed with the proof in two steps: In the first step, we show that for each $W^m_S$, there is always an $s$-biplex $B$ in $G'$, such that $|B \cap W^m_S| \geq \frac{3}{2} m +3$. 

By contradiction, if there is no such $s$-biplex in $G'$. Let $\mathcal{B} = \{B_1, B_2, ..., B_l\}$ be the set of \textit{s}-biplexes in the optimal solution $G'$, such that $|B_i\cap W^m_S| \neq \emptyset$ for $1\leq i \leq l$. According to the assumption, we have $|B_i \cap W^m_S| \leq \frac{3}{2} m + 2$ for all $1\leq i \leq l$. Let $x_i = |B_i \cap U^m_S|$, $y_i = |B_i\cap V^m_S|$, $x_i+y_i \leq \frac{3}{2} m + 2$. Obviously, we have to delete all the edges between $W^m_S \cap B_i$ and $W^m_S - B_i$. Hence the number of edge deletions $C_D$ with respect to $W_S^m$ is at least:

\begin{align*}
C_D & \geq \frac{1}{2} \sum\limits_{i=1}^{l}(x_i(m-y_i)+y_i(m-x_i)) \\
& \geq \frac{1}{2} \sum\limits_{i=1}^{l} (m(x_i+y_i)- \frac{1}{2}(x_i+y_i)^2)& \mbox{(*)} \\
& = \frac{1}{2} \sum\limits_{i=1}^{l}((x_i+y_i)(m- \frac{1}{2} (x_i+y_i))) \\
& \geq \frac{1}{2} \sum\limits_{i=1}^{l}((x_i+y_i)(m- \frac{1}{2} (\frac{3}{2}m+2)))&\mbox{(**)}\\
& = \frac{1}{2} \sum\limits_{i=1}^{l}((x_i+y_i) (\frac{1}{4}m-1)) \\
& = \frac{1}{2} (\frac{1}{4}m-1)\sum\limits_{i=1}^{l}(x_i+y_i) \\
& = m(\frac{1}{4}m-1) = \frac{1}{4}m^2-m &\mbox{(***)}
\end{align*}
The inequality (*) holds since for all integers $x_i>0$ and $y_i>0$, we have $x_iy_i \leq \frac{1}{4} (x_i+y_i)^2$. The inequality (**) is correct because we have  $(x_i+y_i)\leq \frac{3}{2} m +2 $. The equality (***) is correct since we have $\sum\limits_{i=1}^l (x_i+y_i) = |W_S^m| = |U_S^m|+|V_S^m| = 2m$. Thus we know that $|F| \geq \frac{1}{4}m^2 -m$. Consider $|F| - |F'|$, we have: $|F| - |F'| \geq \frac{1}{4}m^2 -m - m(\frac{m+1}{6}) = \frac{1}{4}m^2-\frac{1}{6}m^2-\frac{7}{6}m =  \frac{m}{6}(\frac{m}{2}-7)$.

In our construction, $m = (72+s)n$, thus $\frac{m}{6}(\frac{m}{2}-7) >0$. This contradicts with the assumption that $F$ is optimal. Thereby we have proved that there exists an $s$-biplex $B$ in $G'$ with $|B \cap W^m_S| \geq \frac{3}{2} m +3$. For each $W_S^m$, denote $B_S$ as the $s$-biplex in the optimal solution such that $|B_S\cap W_S^m| \geq \frac{3}{2}m+3$. 

In the second step, we prove the claim that for each $W_S^m$, we have $W_S^m\subseteq B_S \subseteq (W^m_S \cup W_S)$. By contradiction, we assume there is one vertex $x\in W_S^m$, such that $x\notin B_S$. Without loss of generality, we assume $x\in U_S^m$. Since $0\leq |B_S \cap U_S^m| \leq m$, the intersection between $B_S$ and $V_S^m$ must be at least $\frac{3}{2}m+3 - m = \frac{m}{2} +3$, i.e., $|B_S \cap V_S^m|\geq \frac{1}{2}m+3$. Thus to include $x$ into $B_S$, we need at most: (1) Remove the edges between $V_s^m - B_S$ and $x$, and (2) remove the edges between $V_S$ and $x$. This gives a cost $C_I \leq |V_S^m - B_S|+3\leq m - (\frac{m}{2} +3) +3 = \frac{m}{2}$. On the other hand, to have $x$ not in $B_S$, it requires at least to delete all edges between $x$ and $V_S^m\cap B$, which gives a cost $C_D=|V_S^m \cap B_S | = |W_S^m \cap B_S| - |U_S^m \cap B_S| \geq \frac{3}{2}m +3 - m = \frac{m}{2} +3 \geq C_I$. Hence we know that it is always better to include $x$ as part of $B_S$ than to leave $x$ out.

The remaining part of the claim that $B_S \subseteq (W_S^m \cup W_S)$ is proved similarly by contradiction. Suppose there exists a vertex $y \in B_S$ with $y \notin (W_S^m \cup W_S)$. Without loss of generality, we assume $y \in U$. Denote $C_I$ as the cost of including $y$ as a part of $B_S$. Then we have to insert between $y$ and $V_S^m$ at least $(|V_S^m| - s)$ edges. $C_I \geq |V_S^m| - s = m-s$. Consider the cost $C_D$ of removing $y$ from $B_S$. $C_D$ is at most the number of edges between $y$ and $V_S$. Since $|V_S| = 3$, we have $C_D \leq 3 < C_I$, contradicting with the claim of optimal solution. Hence no vertex outside $(W_S \cup W_S^m)$ would end up in $B_S$ in any optimal solution.

W know that for each $W_S^m$, there is an $s$-biplex $B_S$ in the optimal solution, such that $W_S^m \subseteq B_S \subseteq (W_S^m \cup W_S)$. It remains to find out where the vertices in $W_S$ end up. Examine an element $u_i\in U_1$, such that its corresponding element in $A$, $a_i$, is a member of (at least) two subsets $S_1, S_2 \in \mathcal{C}$. In the proof above, we have already shown that $W_{S_1}^m$ and $W_{S_2}^m$ are contained in distinct $s$-biplexes in any optimal solution. Hence we have to delete the edges either between $u_i$ and $V_{S_1}^m$, between $u_i$ and $V_{S_2}^m$ or both. Obviously, if each $u_i$ only connects to one $V_{S}^m$, the total number of edge deletions is at least $3m(|\mathcal{C}| - n)$. For all such vertices in $V_1$, the same argument applies. Hence we have $|F\cap (E_3\cup E_4 \cup E_5)|\geq M$.

Since for each $s$-biplex in $G'$, we have $B_S \subseteq (W_S^m \cup W_S)$, we know that in the optimal solution, every $u_i \in U_1$ is a neighbor of at most three vertices in $V_1$. Since $|U_1|=|V_1| = 3n$, there are at most $9n$ edges between $U_1$ and $V_1$ in the optimal solution. Thereby the edge deletions between $U_1$ and $V_1$ is at least $|F\cap (E_1 \cup E_2)| \geq |E_1|+|E_2|- 9n = |E_2| - 6n = N$.

In conclusion, we have that $|F\cap (E_3\cup E_4 \cup E_5)|\geq M$ and $|F\cap (E_1 \cup E_2)| \geq  N$. Hence $|F| \geq M+N$. Therefore, we know that $F' = F_1\cup F_2\cup F_3$ gives an optimal solution to $s$-BIPLEX EDITING. Finally, let $\mathcal{B}^*$ be a subset of  all $s$-biplexes in the optimal solution, such that $\forall B\in \mathcal{B}^*$, we have $B = W_S^m \cup W_S$. Then $\{S\in \mathcal{C}|B_S\in \mathcal{B}^*\}$ gives a cover to the 3X3C instance. \qed
\end{proof}


\textit{Proof of Lemma \ref{lemma:01}}:

\begin{proof}
By contradiction, suppose we have a vertex $u^* \in R$ with $d(u^*) \leq |T| -s -2$. Then we can find a non-cut vertex $v \in H$. Such vertex must exist, since it is well-known that in an arbitrary graph $G$, there are at least 2 non-cut vertices. Considering $H-v= (R',T',E'')$ , we have 2 cases:

Case i: $v\in N(u^*)$. Then in $H-v$, $d_{H-v}(u^*) = d(u^*)-1 \leq |T|-s-2-1= |T'|-s-2$, $u^*$ is still a forbidden vertex.

Case ii: $v\notin N(u^*)$. Then in $H- v$, $d_{H-v}(u^*) = d(u^*)\leq |T|-s-2= |T'|-s-i$, $u^*$ is still a forbidden vertex.

In summary, either case gives another forbidden subgraph which is a subgraph of $H$, contradicting with $H$ being minimal. \qed \end{proof}


\textit{Proof of Lemma \ref{lemma:03}}:
\begin{proof}
For the first and second claims, the proofs are simple: If a vertex $u\in R_1$ is a non-cut vertex, we can remove $u$ from $H$ without affecting all vertices in $R_0$ being forbidden vertices, thus $H-u$ is still forbidden, contradicting with ``minimal". If a vertex $v\in T_0$ is a non-cut vertex, we can remove $v$ from $H$. In $H-v$, $min\{d_{H-v}(u)\} \leq |T'|-s-1$, thus $H-v$ is still forbidden. For Claim 3, if there is more than one forbidden vertex in $R_0$, all vertices in $R_0$ must be cut vertex, otherwise we could remove an arbitrary vertex in $R_0$ and the resulting graph is still forbidden. 

Next we prove Claim 4. By contradiction, suppose $X_1\cap R_1= \emptyset$. We have $X_1\subseteq R_0$. Then we have two cases:

Case i. $Y_1 = \emptyset$. Then we know that for $u_0\in X_1$, in the original subgraph $H$, $d(u_0) = 1$. Since $u_0$ is in $R_0$, we know by Lemma 1 that in the original subgraph $H$, $\forall u \in R_0$, we have $d(u) = 1$. Therefore, $\forall u \in R_0$, $u$ is a non-cut vertex. Hence we can only have $|R_0| = 1$, since otherwise $R_0$ would contain non-cut vertex and thus contradicts Claim 3. However, since $R_0 = \{u\}$ and $d(u) = 1$, we have $|T_0| = 1$, contradicting with $|T_0| >1$ in Claim 4.

Case ii. $Y_1 \neq \emptyset$. Since $X_1 \cap R_0 \neq \emptyset$, we have $Y_1 \cap T_0 \neq \emptyset$. In subgraph $H_1$, there must be at least two non-cut vertices. Assume a vertex $v\in Y_1$ is a non-cut vertex. then in $H$, $v$ must be a non-cut vertex as well, contradicting Claim 2. Thus we know that there must be at least two vertices $u_1, u_2 \in X_1$, such that $u_1$ and $u_2$ are non-cut vertices of $H_1$. Consider $u_1$ and $u_2$, we have three following properties:(1) In $H$, $u_1$ and $u_2$ must be connected to $v^*$. This is obvious since otherwise $u_1$ and $u_2$ would be non-cut vertices in $H$ as well, contradicting with Claim 3. (2)$\forall x, y \in N(u_1)\backslash \{v^*\}$, there exists a path $P$ in $H_1$ from $x$ to $y$ without passing $u_1$. This is true since otherwise $u_1$ would be a cut vertex in $H_1$. (3)$\forall x\in N(u_1)\backslash \{v^*\}$, there exists a path $Q$ in $H_1$ from $x$ to $u_2$ without passing $u_1$. This is also true since otherwise $u_1$ would be a cut vertex in $H_1$.

Consider two arbitrary neighbours of $u_1$, $x,y \in N(u_1)$. If $x\neq v^*$ and $y\neq v^*$, then we already know that there exists a path $P$ from $x$ to $y$ without passing $u_1$. If $x=v^*$, we can also find a path from $y$ to $v^*$ without passing $u_1$. This is true, because we already know that there exists a path $Q$ from $y$ to $u_2$ and $u_2$ is connected to $v^*$, $Q' = Q \cup\{v^*\}$ is the path. In summary, $\forall x,y \in N(u_1)$ in $H$, there exists a path from $x$ to $y$ without passing $u_1$. Thus $u_1$ is a non-cut vertex in $H$. Moreover, since $u_1 \in R_0$, this contradicting with Claim 3.

Finally, we prove Claim 5. For the purpose of contradiction, suppose $\forall v \in T$,  $d(v)\geq 2$. Consider an arbitrary vertex $u_1\in R_1$. Since $u_1$ is a cut vertex, we can find a connected component $C_1 = (U_{C_1}, V_{C_1}, E_{C_1})$ in $H-{u_1}$, such that all vertices in $V_{C_1}\cap R$ are cut vertices. Such $C_1$ must exist when $|R_0| = 1$. In the case of $|R_1| >1$, we have already proved that all vertices in $R$ are cut vertices in $H$. By the assumption, we have $V_{C_1} \cap R \neq \emptyset$; let $u_2 \in V_{C_1}\cap R$. The fact that $u_2$ is a cut vertex in $H$ leads to that there exists a connected component $C_2= (U_{C_2}, V_{C_2}, E_{C_2})$ in $H-u_2$ which is also a connected component in $H-\{u_1,u_2\}$. Again, by the assumption, $V_{C_2}\cap R\neq \emptyset$; let $u_3\in V_{C_2}\cap R$. The cut vertex $u_3$ implies that there is a connected component $C_3= (U_{C_3}, V_{C_3}, E_{C_3})$ in $H-u_3$, which is a connected component in $H-\{u_1, u_2, u_3\}$. Since $u_1$ and $u_2$ are connected in $H-u_3$. Then $V_{C_3}\cap R \neq \emptyset$. Since $u_1$ and $u_2$ are connected in $H-u_3$, then $V_{C_3}\cap R\neq \emptyset$ follows our assumption. Note that $V_{C_3} \subset V_{C_2} \subset V_{C_1}$. Since $H$ is finite, we will end up with a connected component $C_i = (U_{C_i}, V_{C_i}, E_{C_i}$ where $V_{C_i}\cap R = \emptyset$. However, this would imply that the vertices in $V_{C_i} \cap T$ are degree -1 vertices, contradicting to Claim 2 and our assumption. \qed \end{proof}


\textit{Proof of Theorem \ref{theorem:03}}:

\begin{proof}
Obviously, the problem is in NP. Then the NP-hardness of the problem is shown by a reduction from MAXIMUM BALANCED BICLIQUE (MBB):

\begin{adjustwidth}{1cm}{1cm}
\textbf{Input}: An undirected bipartite graph $G=(U,V,E)$, and and integer $k\geq 0$\\
\textbf{Question}: Does there exist an induced biclique $C^* = (U_{C^*}, V_{C^*}, E_{C^*})$ in $G$, such that $|U_{C^*}| = |V_{C^*}| =k $  ?
\end{adjustwidth}

Given an MBB instance $G = (U,V,E)$ and a nonnegative integer $k$, we construct an EQUAL-SIZE BICLUSTER EDITING (ESBE) instance as follows: (1) Add a set of components $\mathcal{A}$ to $G$, such that\\ $\mathcal{A} = \{A_1, A_2, ... , A_{|U|-k}\}$, $A_i = (U_{A_i}, V_{A_i}, E_{A_i})$, $1\leq i \leq |U|-k$. For each $A_i$, we have $|U_{A_i}| = k-1$, $|V_{A_i}| = k$. We first connect all vertices in $U_{A_i}$ to all vertices in $V_{A_i}$ for $1\leq i \leq |U|-k$, and then connect all the vertices in $U$ to all the vertices in $\bigcup \limits_{A_i \in \mathcal{A}} {V_{A_i}}$. (2) Add a set of components $\mathcal{B}$ to $G$, such that \\ $\mathcal{B} = \{B_1, B_2, ... , B_{|V|-k}\}$, $B_j = (U_{B_j}, V_{B_j}, E_{B_j})$, $1\leq j \leq |V|-k$. For each $B_j$, we have $|U_{B_j}| = k$, $|V_{B_j}| = k-1$. We first connect all vertices in $U_{B_j}$ to all vertices in $V_{B_j}$ for $1\leq j \leq |V|-k$, and then connect all the vertices in $V$ to all the vertices in $\bigcup \limits_{B_j \in \mathcal{B}} {U_{B_j}}$.

Hence, we have the new graph for ESBE $G' = (U', V', E')$: $U' = \bigcup\limits_{A_i \in \mathcal{A}} U_{A_i} \cup  \bigcup\limits_{B_i \in \mathcal{B}} U_{B_i} \cup U$, $V' = \bigcup\limits_{A_i \in \mathcal{A}} V_{A_i} \cup  \bigcup\limits_{B_i \in \mathcal{B}} V_{B_i} \cup V$. The edges of the new graph is: $E' = E_1 \cup E_2\cup E_3\cup E_4 \cup E_5$, with $E_1 = E$, $E_2 = \{\{u,v\}\ |\  u\in U_{A_i} \ \ \wedge \ \  v \in V_{A_i} \}$, $E_3 = \{\{u,v\}\ |\  u\in U_{B_i} \ \ \wedge \ \ v \in V_{B_i}\}$, $E_4 = \{\{u,v\}\ |\  u\in U \ \ \wedge \ \ v \in V_{A_i}\ \ \wedge \ \ 1\leq i\leq |U|-k \}$ and $E_5 = \{\{u,v\}\ |\  u\in V \ \ \wedge \ \ v \in U_{B_i}\ \ \wedge \ \ 1\leq i\leq |V|-k \}$.

The sizes of $U'$ and $V'$ are: $|U'| = k(|U| - k) + k(|V|-k)+k $ and $|V'| = k(|V| - k) + k(|U|-k)+k $. The number of edges is: $|E'| = |E|+k(|U|-k)(|U|+k-1) + k(|V| - k)(|V| +k - 1)$

Let $k'$ and $d$ be the parameters of the new instance: $k' = k(|U|-k)(|U| - 1)+k(|V|-k)(|V| - 1)+|E| - k^2$ and $d  = |U|+|V|-2k+1$. 

``$\Rightarrow$ " Suppose we have found a biclique $C^* = (U_{C^*}, V_{C^*}, E_{C^*})$ in $G$ with $|U_{C^*}| = |V_{C^*}| = k$. Then by the following steps, we can have a solution for the ESBE problem:

(1) For every vertex $u_i \in U\backslash U_{C^*} = \{u_1, u_2, ... u_{|U|-k} \}$, we delete the edges between $u_i$ and all vertices in $A_j$, $i\neq j$. For every vertex $u_i' \in U_{C^*} = \{u_{|U|-k+1}, u_{|U|-k+2}, ..., u_{|U|}\}$, we delete all the edges between $u_i'$ and all vertices in $\bigcup \limits_{A_i \in \mathcal{A}} {V_{A_i}}$. \\
(2) For every vertex $v_i \in V\backslash V_{C^*} = \{v_1, v_2, ... v_{|V|-k} \}$, we delete the edges between $v_i$ and all vertices in $B_j$, $i\neq j$. For every vertex $v_i' \in V_{C^*} = \{v_{|V|-k+1}, v_{|V|-k+2}, ..., v_{|V|}\}$, we delete all the edges between $v_i'$ and all vertices in $\bigcup \limits_{B_j \in \mathcal{B}} {U_{B_j}}$.\\
(3) Delete the edges between $C^*$ and $G - C^*$. 

Let $k_1' = k(|U|-k)(|U| - 1)$, $k_2' = k(|V|-k)(|V| - 1)$ and $k_3'= |E| - k^2$. Clearly, $k_1'+k_2'+k_3' = k'$. More specifically, step (1) requires $k(|U|-k)(|U| - k -1) + k^2(|U| - k) = k(|U| - k)(|U| -1) = k_1'$ edge deletions. Step (2) requires $k(|V| - k)(|V| - k -1)+k^2(|V|-k) = k(|V|-k)(|V|-1) = k_2'$ edge deletions. Step (3) requires $|E| - k^2 = k_3'$ edges deletions. Thus altogether the 3 steps above need $k_1'+k_2'+k_3' = k'$ edge deletions. Obviously the resulting graph contains $|U|+|V|-2k+1$ bicliques. This gives a solution to ESBE instance.

``$\Leftarrow$" Given the ESBE instance, we know $|U'| = |V'| = k(|U|+|V|-2k+1)$. First, we prove that each $A_i$ (or $B_i$) will end up in a separated biclique in the optimal solution. That is, let $\mathcal{D} = \mathcal{A}\cup \mathcal{B}$, for each $D_i \in \mathcal{D}$, in the optimal solution, there exists a biclique $C_i$ such that $D_i\subseteq C_i$ and $D_j\cap C_i = \emptyset $ for all $1\leq i\neq j \leq |U|+|V|-2k$. 

Denote $\mathcal{C} = \{C_1, C_2, ... , C_d\}$ as the $d$ bicliques in the optimal solution and let $C_i= (U_i, V_i, E_i)$. Clearly, the bicliques in $\mathcal{C}$ are $d$ equally-sized balanced bicliques, thus we have $|U_i| = |V_i| = |U'|/d = |U'|/(|U|+|V| + 2k +1) = k$. Thus, the total number of edges in the optimal solution is $dk^2$. Compute the difference between $|E'|$ and the number of edges in the optimal solution, we have:

\begin{align*}
|E'| - dk^2 & = |E|+k(|U|-k)(|U|+k-1) +\\
            & \ \ \ \  k(|V| - k)(|V| +k - 1) - dk^2\\
            & = k(|U| - k)(|U| +k-1 - k) + \\
            &\ \ \ \ k(|V| - k)(|V| +k-1 - k) + \\
            &\ \ \ \ |E| - k^2\\
            & = k'\\
\end{align*}

Since $|E'| - dk^2 = k'$, this indicates that only edge deletions are allowed, otherwise we would have to convert $G'$ into $d$ equally-sized bicliques with more than $k'$ edge modifications. To show that each $D_i$ ends up in a separated biclique, we first show that for every $D_i$, there is a biclique $C_i$ in the optimal solution, such that $D_i \subseteq C_i$. The proof is as follows:

For each $A_i$, we can always find a biclique $C_i$ such that $U_{A_i}\cap U_i \neq \emptyset$ in the optimal solution. Let $u_0 \in (U_{A_i} \cap U_i)$. First, we show that $\forall v \in V_{A_i}$, we have $v\in C_i$. By contradiction, if there exists a vertex $v_0 \in V_{A_i}$ and $v_0 \notin C_i$, since $|V_i| = k$, there must exists a $v_0' \in V_i$ such that $v_0' \notin V_{A_i}$. Then we have to insert at least an edge between $u_0$ and $v_0'$ and thus contradicts with no edge insertion proved above. Second, we prove that $\forall u_0'\in U_{A_i}$, $u_0' \neq u_0$, we have $u_0' \in C_i$. By contradiction, if $u_0' \in C_j$, $i\neq j$, then clearly, we have to insert the edges between $u_0'$ and $V_j$ thus contradicts with no edge insertion. The same proof applies on $B_i$ as well. Therefore, we have proved that, for every $D_i$, there exists a $C_i$ such that $D_i \subseteq C_i$. 

Next, we show that $C_i \cap D_j = \emptyset$ for all $i\neq j$. By contradiction, if there exists an integer $j$, such that $C_i \cap D_j \neq \emptyset$, $i\neq j$, then we have to insert edges in $C_i$ between $D_i$ and $D_j \cap C_i$. This contradicts with no edge insertion. Thereby, we have proved that every $D_i$ ends up in a separated biclique, $1\leq i \leq |U|+|V|- 2k$.

Finally, we prove an optimal solution to ESBE will give a solution to MBB. Without loss of generality, we assume $A_1 \subseteq C_1$. Since $|U_1| = k$ and $|U_{A_1}| = k-1$, clearly there is one vertex $u_1\in C_1$ but $u_1 \notin A_1$. We next discuss where this $u_1$ comes from. As proved above, $u_1$ cannot be from $A_i$, $i>1$ or  any $B_j$, $1\leq j \leq |V|-k$. Thus we have $u_1\in U$. Therefore, for every $A_i$, $1\leq i\leq |U|-k$, there exists one vertex $u_i$ in $U$, such that $u_i$ ends up in the same biclique with $A_i$. Similarly, we can show that for every $B_i$, $1\leq i \leq |V|-k$, there exists one vertex $v_i$ in $V$, such that $v_i$ ends up in the same biclique with $B_i$. That leaves us $|U| - (|U| - k) = k$ vertices in $U$ and $|V| - (|V| - k) = k$ in $V$. If these $2k$ vertices cannot form a balanced biclique in $G'$, then we have to insert edges between them. This would lead to more than $k'$ edge modifications and thus contradicts with the assumption. Therefore, if we have a solution to ESBE instance, we must be able to find a biclique with $k$ vertices in each vertex set in $G$, which gives a solution to the MBB instance.\qed \end{proof}

\textit{Proof of Theorem \ref{theorem:04}}:

\begin{proof}
We reduce ESBE to AVERAGE-\textit{s}-BIPLEX EDITING. First, given an ESBE instance $G=(U,V,E )$, with $k$ as the parameter of maximum number of edge modifications and $d$ as the number of bicliques in the solution, we can safely assume that $|U| = |V|$, an AVERAGE-{s}-BIPLEX EDITING instance $G' = (U',V',E')$ is constructed by adding $d$ components to each of $U$ and $V$, respectively: 

$U' = U \cup U_1\cup U_2 \cup ... \cup U_d$,\\
$V' = V \cup V_1 \cup V_2 \cup ... \cup V_d$.

Let $l =|U|/d $. Each of $U_i$ and $V_i$ contains $d^4l^4s^4$ vertices, i.e.: 

$|U_i| = |V_i| = d^4l^4s^4$.

We denote $W_i = U_i\cup V_i$. For each $U_i$, we divide the vertices in $U_i$ into $d^4l^4s^3$ vertex groups: $U_i = U_i^1 \cup U_i^2 \cup ... \cup U_i^{d^4l^4s^3}$. $|U_i^j| = |U_i^{j'}|$ and $U_i^j \cap U_i^{j'} = \emptyset$ for all $j \neq j'$. Hence we have $|U_i^{j}| = s$ for all $1\leq j\leq d^4l^4s^3$. For each $V_i$, we divide them in the same way. 

$U_i = \bigcup \limits_{j=1} ^{d^4l^4s^3} U_i^{j}$ and $V_i = \bigcup \limits_{j=1} ^{d^4l^4s^3} V_i^{j}$.

Then we connect: (1) all vertices in $ U_i$ to all vertices in $V$, and (2) all vertices in $ U_i$ to all vertices in $U$. Next, inside each $W_i$, we connect all vertices in $U_i^j$ to all vertices in $\bigcup_{j\neq j'} V_{i}^{j'}$, leaving the vertex pairs $\{u,v\}$ with $u\in U_i^j, v \in V_i^j)$ unconnected. Finally, within each $W_i$, we further remove $s\cdot l$ arbitrary edges, which leaves $|U_i|\cdot |V_i| - s\cdot |U_i| - sl = d^8l^8s^8 - s(d^4l^4s^4 +l)$ edges in each $W_i$. The new parameter $k' = k+ 2(d-1)d^5l^5s^4$. Obviously, $G'$ is not an average-$s$-biplex cluster graph and edge modifications are required. Note here we can assume that $1 \leq s < d\cdot l$.

``$\Rightarrow$" If we have a solution for ESBE, i.e., a group of $d$ bicliques with equal size $l$ which costs at most $k$ modifications. Let $\mathcal{B} = \{B_1, B_2, ...,B_d\}$ be the set of $d$ bicliques in the solution. Then a solution for AVERAGE-$s$-BIPLEX EDITING is constructed by disconnecting $B_i$ with all constructed components $W_j$, $1\leq i\neq j\leq d$. Thus each $B_i$ is only connected to $W_i$, $1\leq i\leq d$. This asks for $2(d-1)d^5l^5s^4$ edge deletions. Denote $C_i = B_i \cup W_i$. Since $|C_i \cap U'| = |C_i \cap V'|$, then it is sufficient just to consider the average degree of the vertices in $|C_i \cap U'|$. The average degree in $C_i$ is:

\begin{align*}
\overline{d_{C_i}} = \frac{(|E(U_i, V_i)|+|E(U_i,B_i)|+ |E(V_i,B_i)|+|E(B_i)|)}{(|U_i|+|U' \cap B_i|)}
\end{align*}

Here, $E(U_i,V_i)$ refers to the edges between $U_i$ and $V_i$; $E(U_i,B_i)$ and $E(V_i,B_i)$ refer to the edges between $B_i$ and $U_i$, $B_i$ and $V_i$, respectively; $E(B_i)$  is the set of edges within the biclique $B_i$. According to the construction of $G'$, $|E(U_i,V_i)| = d^8l^8s^8 - s(d^4l^4s^4+l)$, $|E(U_i,B_i)|= |E(V_i,B_i)| = s^4d^5l^5$. Since $B_i$ is biclique, we have $|E(B_i)| = l^2$. Hence,:

\begin{align*}
\overline{d_{C_i}} & = \frac{(|E(U_i, V_i)|+|E(U_i,B_i)|+ |E(V_i,B_i)|+|E(B_i)|)}{(|U_i|+|U' \cap B_i|)}\\
&= \frac{d^8l^8s^8 - s(d^4l^4s^4+l)+2d^4l^5s^4+l^2}{l+d^4l^4s^4}\\
&= \frac{(d^4l^4s^4 +l)^2 - s(d^4l^4s^4+l)}{d^4l^4s^4+l}\\
&= d^4l^4s^4 - s\\
&= |V_i|+| V' \cap B_i| - s
\end{align*}

This average degree satisfies the average-$s$-biplex. This will give a solution to AVERAGE-$s$-BIPLEX EDITING instance.

``$\Leftarrow$". We firstly prove that for each $W_i$ there is an average-$s$-biplex $D_i$ in the optimal solution, such that $W_i \subseteq D_i$, $1\leq i \leq d$ and $W_j \cap  D_i = \emptyset$ for $1\leq j\leq d$, $i\neq j$. In order to prove this claim, we proceed in several steps. First, we prove that, for each $W_i$, there exists an average-$s$-biplex $D_i$ and $|D_i \cap W_i| \geq d^4l^4s^4$.

By contradiction, if there does not exist such an average-$s$-biplex in the optimal solution. Denote $\mathcal{D} = \{D_1, D_2, ...,D_r\}$ as the set of average-$s$-biplexes in the optimal solution, $r\geq 1$. Then we have $\forall D_j \in \mathcal{D}$, $|W_i \cap D_i| < d^4l^4s^4$, $1\leq j \leq r$, $1\leq i\leq d$. Specifically, consider $W_1$, without loss of generality, let $\mathcal{D}' = \{D_1, D_2, ...,D_t\}$, $1\leq t\leq r$ be the set of average-$s$-biplexes in the optimal solution that intersect with $W_1$. Let $X_i = U_1 \cap D_i$, and $Y_i = V_1 \cap D_i$, $1\leq i \leq t$. Thus we have to delete the edges between different average-$s$-biplexes. The corresponding number of edge deletions $C_D$ is:
\begin{align*}
C_D & \geq \frac{1}{2} \sum\limits_{i=1}^{t} (|X_i|(|V_1|-|Y_i|) + |Y_i|(|U_1|-|X_i|)) - s(d^4l^4s^4+l)\\
    & = \frac{1}{2} \sum\limits_{i=1}^{t} (|X_i|(d^4l^4s^4-|Y_i|) + |Y_i|(d^4l^4s^4-|X_i|)) \\
    & - s(d^4l^4s^4+l)\\
    & = \frac{1}{2}\sum\limits_{i=1}^{t} (d^4l^4s^4(|X_i|+|Y_i|) - 2|X_i||Y_i|) - s(d^4l^4s^4+l)\\
    & \geq \frac{1}{2}\sum\limits_{i=1}^{t} (d^4l^4s^4(|X_i|+|Y_i|) - \frac{1}{2}(|X_i|+|Y_i|)^2)\\
    & - s(d^4l^4s^4+l) \ \ \ \  (*)\\
    & \geq \frac{1}{2}\sum\limits_{i=1}^{t}(d^4l^4s^4(|X_i|+|Y_i| - \frac{1}{2}|X_i| - \frac{1}{2}|Y_i|))\\
    &- s(d^4l^4s^4+l) \ \ \ \ (**)\\
    & = d^4l^4s^4\cdot \frac{1}{2}\sum\limits_{i=1}^{t}(\frac{1}{2}(|X_i|+|Y_i|))- s(d^4l^4s^4+l)\\
    & = \frac{1}{2}d^8l^8s^8 - s(d^4l^4s^4 +l)\ \ \ \  (***)
\end{align*}

Inequality (*) holds because for an arbitrary pair of integers $(a,b)$ that are greater than 0, we have $ab \leq \frac{1}{4} (a+b)^2$. Inequality (**) holds because we assume $|X_i|+|Y_i| < d^4l^4s^4$ for all $i$, thus $d^4l^4s^4(|X_i|+|Y_i|) - \frac{1}{2}(|X_i|+|Y_i|)^2 < d^4l^4s^4(|X_i|+|Y_i|) - \frac{1}{2}\cdot  d^4l^4s^4 (|X_i|+|Y_i|)$. Equality (***) holds since we have $\sum\limits_{j=1}^{t}(|X_i|+|Y_i|) = |U_1|+|V_1| = 2d^4l^4s^4$. Obviously, when $d\geq 2$, $l\geq 1$, $s\geq 1$, we have $C_D > k'$, contradicting with the assumption that $D$ is a solution.

Denote $D_1$ as the average-$s$-biplex such that $|D_1 \cap W_1| \geq d^4l^4s^4$. Let $X_1 = D_1 \cap U_1$ and $Y_1 = D_1 \cap V_1$. Next, we prove that $|X_1|\geq \frac{1}{3}d^4l^4s^4$ and $|Y_1| \geq \frac{1}{3}d^4l^4s^4$. 

By contradiction, assume $|X_1| < \frac{1}{3}d^4l^4s^4$. Then we have to delete all the edges between $W_1\cap D_1$ and $W_1 - D_1$. The cost for edge deletions $C_D$ is lower-bounded by:
\begin{align*}
C_D & \geq |X_1|(|V_1|-|Y_1|) + |Y_1|(|U_1|-|X_1|) - s(d^4l^4s^4+l)\\
& \geq d^4l^4s^4(|X_1|+|Y_1|) - \frac{1}{2}(|X_1|+|Y_1|)^2 - s(d^4l^4s^4 +1)\\
& \geq d^4l^4s^4 \cdot \frac{4}{3} d^4l^4s^4 - \frac{1}{2} \cdot \frac{16}{9} d^8l^8s^8 - s(d^4l^4s^4 +1)\ \  (*)\\
& = \frac{4}{9}d^8l^8s^8 - s(d^4l^4s^4 +1) \geq k'
\end{align*}
Inequality (*) holds, since $d^4l^4s^4(|X_1|+|Y_1|) - \frac{1}{2}(|X_1|+|Y_1|)^2$ reaches the maximum value within the range of $0\leq |X_1| \leq \frac{1}{3} d^4l^4s^4$ and $\frac{2}{3}d^4l^4s^4 \leq |Y_1| \leq d^4l^4s^4$, when $|X_1| = \frac{1}{3} d^4l^4s^4$, $|Y_1| = d^4l^4s^4$. Thus we have a cost of edge deletion greater than $k'$, contradicting with the assumption. Hence it is proved that $|X_1|,|Y_1| \geq \frac{1}{3}d^4l^4s^4$.

Next, consider $D_1$, let $P = (\bigcup \limits_{j=2}^{d} U_j \cap D_1)$ and $Q = (\bigcup \limits_{j=2}^{d}V_j \cap D_1)$. That is, $P$ and $Q$ together represent the set of vertices in $D_1$ and in all other $W_j$s, $1<j\leq d$. Next, we prove: $|P| \leq 4s$ and $|Q| \leq 4s$.

Since the vertices in $P$ and $Q$ belong to other $W_j$s, $1<j\leq d$, thus to include them in $D_1$, we have to insert a certain number of edges between $P$, $Q$ and $W_1$. Denote $X_1^* = U \cap D_1$ and $Y_1^* = V\cap D_1$. We compare the cost of insertions to include these vertices into $D_1$ and the cost of deletions to remove them out from $D_1$. Note in the following computation, we compute only the average degree for the vertices in $U'\cap W_1$, since the average degree for $V'\cap W_1$ gives the same result. To meet the condition of average degree, the insertion cost $C_I$ is lower-bounded as follows:
\begin{align*}
C_I & \geq (|D_1\cap U'|-s)|D_1 \cap V'| - \max\{|E(D_1\cap U', D_1\cap V')|\}\\
& \geq ((|Q|+|Y_1|+|Y_1^*|)-s)(|P|+|X_1|+|X_1^*|) - \\
& \ \ \ \ ((|Q|+|Y_1|+|Y_1^*|)(|P|+|X_1|+|X_1^*|) - |P||Y_1| - |Q||X_1|)\ \ \ (*) \\ 
& \geq (|Y_1|-s)|P|+(|Q|-s)|X_1|-s|X_i^*| 
\end{align*}

Inequality (*) holds because to lower-bound $C_I$, we use the maximum value of $|E(D_1\cap U', D_1\cap V')|$. However, for edge deletions, we only need: 
\begin{align*}
C_D & = |P||Y_1^*| + |Q||X_1^*|
\end{align*}

Thus, we have:
\begin{align*}
C_I-C_D & \geq (|Y_1| - |Y_1^*|-s)|P| + (|Q|-s)(|X_1|-|X_1^*|) - \\
& 2s|X_1^*|\\
\end{align*}

By contradiction, we assume $|P| \geq 4s$, then:
\begin{align*}
C_I-C_D & \geq 4s|Y_1| - 4s^2 - 4s|Y_1^*| + (|Q|-s)(|X_1| -|X_1^*|) -\\
& \ \ \ \ 2s|X_1^*| \\
& \geq 4s|Y_1| - 4s^2 - 4s|Y_1^*| - s|X_1| - 2s|X_1^*|\ \ \ (*)\\
& \geq 4s\cdot \frac{1}{3} d^4l^4s^4 - 4s^2 - 4s|Y_1^*| - s\cdot d^4l^4s^4 \\
& \ \ \ -2s\cdot dl\ \ (**) \\
& \geq \frac{4}{3}d^4l^4s^5 - 4s^2 - 4sdl -d^4l^4s^5 - 2sdl \\
& \geq \frac{1}{3}d^4l^4s^5 - 4s^2 - 5sdl >0
\end{align*}
In inequality (*), we have $(|Q|-s)(|X_1| -|X_1^*|) = -s|X_1| + |Q|(|X_1| - |X_1^*|) + s|X_1^*|\geq - s|X_1|$. In inequality (**), we have $|Y_1| \geq \frac{1}{3} d^4l^4s^4$, $|X_1|\leq d^4l^4s^4$, $|X_i^*|\leq dl$ and $|Y_i^*|\leq dl$. This $C_I-C_D$ is clearly greater than $0$, indicating it is better to remove all vertices in $P$ and $Q$. Thus we know that $|P|\geq 4s$, we could remove all vertices in $P$ and $Q$ out from $D_1$, contradicting with $\mathcal{D}$ is an optimal solution.

By contradiction, if $|Q| \geq 4s$, then:
\begin{align*}
C_I - C_D & \geq (|Y_1| - |Y_1^*|-s)|P|+ 3s\cdot(|X_1| -|X_1^*|) - 2s|X_1^*|\\
 & \geq 3s\cdot(|X_1| -|X_1^*|) - 2s|X_1^*|\\
 & \geq 3s( \frac{1}{3}d^4l^4s^4 - dl) - 2sdl \ \ \ (*)\\
 & = d^4l^4s^5 - 5sdl >0
\end{align*}

Inequality (*) is correct since $|X_1| \geq \frac{1}{3}d^4l^4s^4$ and $|X_1^*| \leq dl$. Thus we know that $|Q|$ cannot be greater than $4s$. Thus we proved that both $|P|$, $|Q|$ are smaller than $4s$, otherwise it would need less cost to delete these vertices from $D_1$ than to include them in $D_1$. 

Now based on the claims above, we prove that $\forall u\in W_1$, we have $u\in D_1$. We prove this by comparing the cost of including an arbitrary vertex $u \in W_1$ into $D_1$ ($C_I$) and the cost of removing $u$ from $D_1$ ($C_D$). Without loss of generality, we assume $u\in U_1$. For $u$, the cost of removing $u$ from $D_1$ is at least the edges between $u$ and $Y_1$: $C_D  \geq |Y_1| - s - sl \geq \frac{1}{3}d^4l^4s^4 - s- sl $.

To include the $u$ into $D_1$, we need to delete the edges between $u$ and the vertices outside $D_1$, insert all the missing edges incident to $u$ and insert the missing edges between $u$ and $Q$: $C_I  \leq |Y_1^*|+s+sl+4s \leq dl+5s+sl $. Clearly, $C_D>C_I$, then we conclude for each $u \in W_1$, we have $u \in D_1$ in the optimal solution, i.e., $W_1\subseteq D_1$. Next we prove that for each vertex $v \in \bigcup\limits_{1\leq i\leq d} W_i \backslash W_1$, we have $v \notin D_1$ in any optimal solution. In order to show this claim, we compare the cost of including $v$ into $D_1$ ($C_I$) and the cost of deleting $v$ from $D_1$ ($C_D$). Without loss of generality, we assume $v \in U'$. To have $v$ in $D_1$, we have to keep the average degree satisfying the criteria:

\begin{align*}
C_I & \geq (1+|X_1|+|X_1^*|+|P|)(|Y_1|+|Y_1^*|+|Q|) \\
	&-((1+|P|+|X_1|+|X_1^*|)(|Q|+|Y_1|+|Y_1^*|)- s(|Y_1|+l)-|Y_1|)\\
    & = |Y_1| + sl -s|V_1^*| - 4s\\
    & \geq d^4l^4s^4+sl-sdl - 4s
\end{align*}

And to remove $v$ from $D_1$, we just need to delete at most the edges between $v$ and $Y_1^*$ and the edges between $v$ and $Q$: $C_D \leq dl+4s $. Obviously, we have $C_I > C_D$, thus it is better to remove every $u\notin W_1$ from $D_1$. In summary, we have proved that there are $d$ disjoint components in the optimal solution, each of which contains one $W_i$. For each vertex $u \in G$, in the optimal solution $u$ must be connected to one of the $d$ components. This asks for $k'-k = 2(d-1)d^5l^5s^4$ edge deletions. 

Finally, we show that for all $D_i$, we have $|D_i \cap U| = |D_i \cap V| = l$. First, we prove that $|D_i \cap U| \geq l$ and $|D_i \cap V|\geq l$, for all $1\leq i \leq d$. By contradiction, if $|D_i \cap U|<l$, then the average degree of the vertices in $D_i\cap U'$ is upper-bounded by:

\begin{align*}
\overline{d_{D_i\cap U'}} & \leq \frac{|D_i\cap V'|\cdot |D_i\cap U'| - s(d^4l^4s^4+l)}{|D_i\cap U'|}\\
                          &  = |D_i \cap V'| - \frac{s(d^4l^4s^4 +l)}{|D_i \cap U'|}\\
                          & < |D_i \cap V'| - s \ \ \ \ (*)
\end{align*}

Inequality (*) holds since $|D_i\cap U|<l$ and thus we have $|D_i \cap U'|\leq (d^4l^4s^4 +l)$. This contradicts with optimal solution. Similarly, we can prove that $|D_i \cap V|\geq l$ for all $1\leq i \leq d$. Since $|U| = |V| = dl$ and there are $d$ bicliques in the optimal solution, we know that $|D_i\cap U| = |D_i\cap V| = l$. Moreover, in the optimal solution, the induced subgraph $G'[D_i \cap (U\cup V)]$ must form a biclique, otherwise $D_i$ would not be an average-$s$-biplex. Thus, this requires that $G$ be transformed into $d$ equally-sized balanced bicliques within $k$ edge modifications. Therefore, in summary, in the optimal solution, $G$ must be converted into $d$ disjoint equal-size bicliques and thus gives a solution to ESBE instance.\qed
\end{proof}



\textit{Proof of Lemma \ref{lemma:05}}:


\begin{proof}
Obviously, to separate $u$ and $v$, we must not allow $u$ and $v$ to have any common neighbors. Thus at least $d = \min\{\omega(u, S(u,v)), \omega(v,S(u,v))\}$ deletions are required. If $d>k$, then we cannot afford the cost of deletions. Hence $u$ and $v$ must end up in the same average-$s$-biplex.\qed
\end{proof}

\textit{Proof of Lemma \ref{lemma:06}}:
\begin{proof}
Without loss of generality, let $L \subseteq N^*(u)$ be the subset of $N^*(u)$ that end up in the same average-$s$-biplex  as  $u$, and $M = N^*(u) \backslash L$. Thus we have $|M| \leq k$, since otherwise we would have to delete more than $k$ edges between $M$ and $u$. Thus $|L| \geq |N^*(u)| - k$. Note that the vertices in $M$ and $L$ are ``\textit{interchangeable}", i.e. for any vertex $m\in M$ and $l\in L$, we can exchange the locations of $m$ and $l$, by putting $m$ in $L$ and $l$ in $M$. Such location-exchange requires no further edge modification. Suppose in an optimal solution, $m\in M$ is connected to a set of vertices $Z$. Obviously, $u\notin Z$. Thus to reconnect $m$ to $u$, we have to re-insert the deleted edge between $u$ and $m$, and remove all the inserted edges between $m$ and $Z$. That saves $|Z|+1$ edge modifications. Next, to move $l$ out and connect $l$ with $Z$, we have to delete the edge between $l$ and $u$, and insert the edges between $l$ and $Z$. This procedure requires $|Z| +1$ edge modifications. Therefore, $M$ and $L$ are interchangeable. Let $N^*(u) = \{v_1, v_2, ..., v_r\}$, $r\geq k+1$. We can claim that the vertex set $L' = \{v_{k+1}, ..., v_r\}$ is a subset of $L$ and all vertices in $L'$ end up in the same average-$s$-biplex with $u$. This claim is true because we cannot afford deleting the edges between $u$ and more than $k$ vertices in $N^*(u)$. Since all vertices in $L'$ end up in the same average-$s$-biplex, we can merge them together. Thus, Rule 3. is correct.\qed
\end{proof}

\textit{Proof of Theorem \ref{theorem:05}}:

\begin{proof}
Let $G$ be a connected component in the optimal solution after applying the reduction rules exhaustively. Since we have removed all existing average-$s$-biplexes, $G$ must be incident to edge modifications. Thus there exist at most $2k$ connected components. Let $G=(U,V,E)$ and without loss of generality, we assume $|U|\leq |V|$. First we prove $|U| \leq 4k+6s$.

By contradiction, if $|U|>4k+6s$, then obviously we have $|V| > 4k+6s$. Let $u^*$ be the vertex in $U$ that has the largest degree. Obviously, $d'(u^*)\geq \sigma(V)-s\geq |V|-s$. We distinguish in two cases:

Case i: $\sigma(u^*) > \frac{1}{2} \sigma(U) > 2k+3s$. Note that for all edges incident to $u^*$, we can have at most one edge with weight larger than $k$. This is true because by contradiction, if we have $v_1$, $v_2 \in V$ and $\omega(u^*,v_1)>k$, $\omega(u^*, v_2)>k$, then we could merge $v_1$ and $v_2$ by Rule 2. Since $u$ has at least $|V| -s $ neighbors, we can compute the number of missing edges $m_e$ incident to $u$ as:
\begin{align*}
m_e& \geq (|V|-s-1)(\sigma(u^*)-k) \ \ (*)\\
   & > (4k+5s-1)\cdot \sigma(u^*)/2 \\
   & > 4s \cdot \sigma(u^*)/2\\
   & \geq 4s\cdot \sigma(U)/4\\
   & =s \cdot \sigma(U)
\end{align*}

Thus the average degree of $U$ is :
\begin{align*}
\overline{d(U)} &< \frac{\sigma(U)\cdot\sigma(V) -s \cdot \sigma(U) }{\sigma(U)} \\
 & =\sigma(V) - s
\end{align*}

Inequality (*) holds because there can be at most one edge incident to $u^*$ with edge weight larger than $k$ and then for the rest of the neighbors (at least $|V|-s-1$ vertices), each of them is incident to at least $(\sigma(u^*)-k)$ missing edges. Hence $G$ does not satisfy average-$s$-biplex, we have a contradiction. 

Case ii: $\sigma(u^*) \leq \frac{1}{2}\sigma(U)$. Then we first prove that there must exist another vertex $u'$, such that $\omega(u',V) \geq |V|-2s$. Suppose there does not exist such a vertex, then we compute the number of missing edges $m_e$:
\begin{align*}
m_e &> (\sigma(V) - (|V| - 2s ))(\sigma(U)- \sigma(u^*)) \ \ (*)\\
    &> 2s\cdot \sigma(U)/2\\
    &> s\cdot \sigma(U)
\end{align*} 

Thus the average degree of $U$ is smaller than $\sigma(V)-s$. Inequality (*) holds because the degrees of the vertices other than $u^*$ in $U$ are all smaller than $|V|-2s$. Then for each of such vertices, there are at least $\sigma(V)-(|V|-2s)$ missing edges incident to it. Hence we proved that there must be a vertex $u'$ with $d'(u') \geq |V|-2s$. Consider $u^*$ and $u'$, the number of shared neighbors between them is at least:
\begin{align*}
&\geq |V|-s+|V|-2s - |V|\\
&\geq |V|-3s\\
&\geq 4k+3s >k
\end{align*}

This contradicts with Rule 2., since we can merge $u^*$ and $u'$ together. So far, we have proved that $|U| \leq 4k+6s$. Next we show $|V|$ cannot be larger than $(4k+6s)\cdot s+k$ vertices. 

By contradiction, assume $|V| > (4k+6s)\cdot s +k$. Since $G$ is already an average-$s$-biplex, there can be at most $\sigma(U)\cdot s\leq s(4k+6s)$ missing edges in $G$. Hence in $V$, there can be at most $s(4k+6s)$ vertices incident to missing edge(s). By $|V|>(4k+6s)\cdot s +k$, there are at least $k$ vertices that are connected to all vertices in $U$. If $|U| \geq 2$, then for every pair of vertices in $U$, they share more than $k$ common neighbors in $V$, contradicting with Rule 2. That leaves the only case of $|U|=1$. Let $U = \{u\}$, We consider two sub-cases:

Case i: If $\sigma(u) > k$, then there are at least $k$ vertices in $v\in V$, such that $\omega(v,U) > k$. This contradicts with Rule 2.

Case ii: If  $\sigma(u) \leq k$, then we prove the claim that: $\forall v\in V$, $\sigma(v) = 1$. By contradiction, assume if there exists a vertex $v'$ such that $\sigma(v')>1$. Then consider two vertices $v_1$, $v_2 \in \delta(v')$, $\sigma(v_1) = 1$, $\sigma(v_2) = 1$. We must have the common neighbors of $v_1$ and $v_2$ be a subset of $\delta(u)$, i.e., $S(v_1,v_2) \subseteq \delta(u)$. Thus $|S(v_1,v_2)|<k$. Then we have $\omega( v_1, S(v_1,v_2)) < k$ and $\omega(v_2, S(v_1, v_2)) < k$. Thus $v_1$ and $v_2$ would not be merged, contradicting with Rule 2. Since we proved that $\forall v\in V$, $\sigma(v) = 1$, then $|V|$ cannot be bigger than $k+1$; otherwise we could apply Rule 3. to reduce it. 

In summary, we proved that $|U|\leq 4k+6s$ and $|V| \leq (4k+6s)\cdot s +k$. Then the total number of vertices in $G$ is at most $2k(((s+1)(4k+6s))+k)$. \qed \end{proof}




\textit{Proof of Theorem \ref{theorem:06}}:
\begin{proof}
For $s=0$, the problem is equivalent to BICLUSTER EDITING problem and thus is NP-complete. For any $s$>1, we give a reduction from BICLUSTER EDITING. The same construction also works for $s$-DEFECTIVE BICLUSTER DELETION.

Given a BICLUSTER EDITING instance: a bipartite graph $G= (U,V,E)$ and a nonnegative integer $k$, we construct a new graph $G'$ by adding $n$ components ($n = |U|+|V|$) to $G$: $\{W_1,W_2,..., W_n\}$. $W_i =(U_i, V_i, E_i)$, $|U_i| = |V_i| = n^4+s$. We connect all vertices $u \in U_i$ to all vertices $v\in V$, all vertices $v\in V_i$ to all vertices $u\in U$. Inside each $W_i$, we have $|E_i| = |U_i||V_i| - s$ edges, i.e. insert all but $s$ edges. The parameter $k'$ is equal to $k+n(n-1)(n^4+s)$.

``$\Rightarrow$" Let ${B_1,B_2,...,B_l}$ be the $l$ $(l<n)$ bicliques in the optimal solution for the BICLUSTER EDITING instance. Then for all $v \in B_i$ $(1\leq i \leq l)$, remove all the edges between $v$ and $W_j$ for all $i\neq j$, $1\leq j \leq n$. Denote $G^*$ as the result graph from $G'$ after the edge deletions. Clearly, $G^*$ is an $s$-defective bicluster. Moreover, the total number of edge modifications is equal to the edge modification used for bicluster editing in $G$ plus the edge deletions afterwards: $k' = k +n(n-1)(n^4+s)$, satisfying the edge modification upper-bound. Hence we have a solution for $s$-DEFECTIVE BICLUSTER EDITING instance.

``$\Leftarrow$" Let $\{D_1, D_2,..., D_r\}$, $r\geq 1$ be the connected components in an optimal solution of $G'$. Denote the resulting graph as $G^*$. Clearly, each $D_i$, $1\leq i\leq r$, is an $s$-defective biclique.

In order to prove solution for $s$-DEFECTIVE BICLUSTER EDITING is also optimal solution for BICLUSTER EDITING, we first show for every $W_i$ with $1\leq i \leq n$, there is a $D_i$ such that $W_i \subseteq D_i$ and $D_i \cap W_j = \emptyset$ for all $1\leq j\neq i \leq n$. By contradiction, we assume this is not the case. Then there must exist at least one $W_i$, we assume it to be $W_1$, such that there is no $D_i$ completely containing $W_1$ in $G^*$. Without loss of generality, we assume that $\mathcal{D} = \{D_1, D_2, ..., D_t\}$, $1\leq t\leq r$, is the set of components that intersect with $W_1$. We then claim that there exists a $D_j$, such that $|D_j \cap W_1| \geq (n^4+s)$, $1\leq j\leq t$. Denote $X_j = D_j \cap U_1$ and $Y_j = D_j \cap V_1$. If we have $|D_j \cap W_1| < (n^4+s)$, for all $1\leq j \leq t$, then the edges between $W_1 \cap D_j$  and $W_1 \backslash D_j $ must be deleted. Thus the number of edge deletions $C_D$ that we need:
\begin{align*}
C_D & \geq \frac{1}{2} \sum\limits_{j=1}^t (|X_j|(|V_1| - |Y_j|) + |Y_j| (|U_1| - |X_j|)) - s\\
    & = \frac{1}{2} \sum\limits_{j=1}^t ((n^4+s)(|X_j+|Y_j|) - 2|X_j||Y_j|) - s\\
    & \geq \frac{1}{2} \sum\limits_{j=1}^t ((n^4+s)(|X_j+|Y_j|) - \frac{1}{2}(|X_j|+|Y_j|)^2) -s\\
    & > \frac{1}{2} \sum\limits_{j=1}^t((n^4+s)(|X_j|+|Y_j| - \frac{1}{2}|X_j| - \frac{1}{2}|Y_j|)) - s\ \  (*)\\
    & = \frac{1}{4}(n^4+s) \sum\limits_{j=1}^t(|X_j|+|Y_j|) - s\\
    & = \frac{1}{4}(n^4+s)^2 - s \geq k'
\end{align*}

Inequality (*) is correct since we assume $|D_j \cap W_1| < n^4+s$, for all $1\leq j \leq t$. Thus we have $\frac{1}{2}(|X_j|+|Y_j|)^2 < \frac{1}{2}(n^4+s)(|X_j|+|Y_j|)$. The above inequality shows that if we have $|D_j \cap W_1|< n^4+s$ for all $1\leq j \leq t$, then we need more than $k'$ edge modifications, contradicting with the assumption of optimal solution. Thus we know that, for each $W_i$, there exists a $D_j$ such that $|W_i \cap D_j| \geq (n^4+s)$. Consider $W_1$. Let $D_1$ be the component such that $|W_1 \cap D_1| \geq (n^4+s)$. We next prove that $|X_1| > \frac{1}{3}(n^4+s)$ and $|Y_1| > \frac{1}{3}(n^4+s)$. 

By contradiction, without loss of generality, we assume $|X_1| \leq \frac{1}{3} (n^4+s)$. Then we compute the cost of deletions within $W_1$:
\begin{align*}
C_D & \geq |X_1|(|V_1| - |Y_1|) + |Y_1|(|U_1| - |X_1|) - s\\
    &  = (n^4+s) (|X_1| + |Y_1|) - 2|X_1||Y_1| - s\\
    &  \geq (n^4+s)(|X_1| + |Y_1|) - \frac{1}{2}(|X_1| + |Y_1|)^2 - s\\
    & \geq \frac{4}{3}(n^4+s)^2 - \frac{8}{9}(n^4+s)^2 - s \ \  (*)\\
    & = \frac{4}{9} (n^4+s)^2 - s \geq k'\\
\end{align*}

In the inequality (*), we compute the minimum value for $(n^4+s)(|X_1| + |Y_1|) - \frac{1}{2}(|X_1| + |Y_1|)^2 $, within the range of $0\leq |X_1| \leq \frac{1}{3}(n^4+s)$, $\frac{2}{3}(n^4+s) \leq |Y_1| \leq n^4+s$. The result shows that we must have more than $k'$ edge modifications if $|X_1|$ or $|Y_1|$ is at most $\frac{1}{3} (n^4+s)$, thus contradicting with the assumption of optimal solution.

Next, based on the claims proved above, we show that: (1) $W_1\subseteq D_1$ and (2) for all $j$ that $j\neq 1$, we have $W_j \cap D_1 = \emptyset$, $1<j\leq n$. First, for each $u \in W_j$ $1<j\leq n $, we prove $u \notin D_1$. We compute the $C_I$ as the cost of including $u$ into $D_1$ and the cost $C_D$ as the cost of removing $u$ from $D_1$. Without loss of generality, we assume $u \in U_j$:

\begin{align*}
C_I & \geq  |D_1| - s \\
   & \geq \frac{1}{3}(n^4+s) - s\\
C_D & \leq |V| \leq n\\
\end{align*}

Obviously, $C_I > C_D$, thus it is better to remove such $u$ from $D_1$. Similarly, for each $v\in W_1$ we compute the cost  $C_I$ of including it into $D_1$ (to delete edges connecting $v$ and the vertices outside $D_1$), and the cost $C_D$ of removing $v$ out from $D_1$. Without loss of generality, we assume $v\in U_1$:
\begin{align*}
C_I & \leq |V| \leq n\\
C_D & \geq |D_1| -s \\
 & \geq \frac{1}{3}(n^4+s) - s\\
\end{align*}
Clearly, it is better to include these vertices as part of $D_1$. So far, we have proved that for each $W_i$, there is one $D_i$ such that $W_i \subseteq D_i$. Hence in the optimal solution, we have at least $n$ components, which requires $k'-k$ deletions. If $G$ cannot be edited within $k$ edge modifications into disjoint set of bicliques, there must be more than $s$ missing edges in some component in the result graph $G^*$. Thus we must be able to modify $G$ into a set of disjoint bicliques, in order to have an optimal solution for $s$-DEFECTIVE BICLUSTER EDITING. In conclusion, if we have an optimal solution for $s$-DEFECTIVE BICLUSTER EDITING, then the induced subgraph of the result graph $G^*[U\cup V]$ gives a solution to BICLUSTER EDITING. \qed \end{proof}



%
% Modify the bibliography environment to call for the author-year
% system. This is done normally with the citeauthoryear option
% for a particular contribution.
\makeatletter
\renewenvironment{thebibliography}[1]
     {\section*{\refname}
      \small
      \list{}%
           {\settowidth\labelwidth{}%
            \leftmargin\parindent
            \itemindent=-\parindent
            \labelsep=\z@
            \if@openbib
              \advance\leftmargin\bibindent
              \itemindent -\bibindent
              \listparindent \itemindent
              \parsep \z@
            \fi
            \usecounter{enumiv}%
            \let\p@enumiv\@empty
            \renewcommand\theenumiv{}}%
      \if@openbib
        \renewcommand\newblock{\par}%
      \else
        \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}%
      \fi
      \sloppy\clubpenalty4000\widowpenalty4000%
      \sfcode`\.=\@m}
     {\def\@noitemerr
       {\@latex@warning{Empty `thebibliography' environment}}%
      \endlist}
      \def\@cite#1{#1}%
      \def\@lbibitem[#1]#2{\item[]\if@filesw
        {\def\protect##1{\string ##1\space}\immediate
      \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces}
\makeatother
%

\end{document}
